我有一个列表,我想从中随机选择一个节点。因为它不是一个数组,所以我事先不知道它的长度。有没有办法随机选择一个节点(均匀分布)而不必扫描整个列表(在最坏的情况下)两次(即获取它的长度并在随机选择其位置后到达所选节点)?
这是我用于列表的代码:
struct mynode {
in_addr_t paddr;
struct mynode *prev, *next;
};
struct mylist {
struct mynode *first, *last;
char *name;
};
最佳答案
正如 joop 的评论中所建议的那样和 Ilja Everilä , 我实现了 reservoir sampling 在 C 中。
struct mynode *select_mynode(struct mylist *list) {
struct mynode *list_iter = list->first; // An iterator to scan the list
struct mynode *sel_node = list_iter; // The node that will be selected
int count = 2; // Temporary size of the list
srand((unsigned int) time(NULL)); // Seed
// Select a random element in O(n)
while (list_iter->next != NULL) {
if (rand() % count == (count - 1))
sel_node = list_iter->next;
list_iter = list_iter->next;
count++;
}
return sel_node;
}
注意:有关随机选择的更多信息,请参阅 here .
关于c - 从 C 中的列表中选择一个随机节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43778516/