Thread overview | |||||||||
---|---|---|---|---|---|---|---|---|---|
|
March 25, 2015 Keep Track of the Best N Nodes in a Graph Traversal Algorithm | ||||
---|---|---|---|---|
| ||||
I have graph traversal algorithm that needs to keep track of the N "best" node visit. Every time a visit a new node I get its goodness along with a ref to it. I then want to compare it to every currently best node in this list and replace it with the worst one if its better than the worst. How do I most easily do this with regards to minimizing GC-usage. For N = 3 I mean something like this: (A,1) => [(A,1)] (B,2) => [(A,1), (B,2)] (C,3) => [(A,1), (B,2), (C,3)] (X,0) => [(X,0), (A,1), (B,2)] (Y,1) => [(X,0), (Y,1), (A,1)] ... (A,1) means we just visited node with goodness (distance) 1 |
March 25, 2015 Re: Keep Track of the Best N Nodes in a Graph Traversal Algorithm | ||||
---|---|---|---|---|
| ||||
Posted in reply to Per Nordlöw | Nordlöw:
> I have graph traversal algorithm that needs to keep track of the N "best" node visit.
std.algorithm.topNCopy?
Bye,
bearophile
|
March 25, 2015 Re: Keep Track of the Best N Nodes in a Graph Traversal Algorithm | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | On Wednesday, 25 March 2015 at 13:55:29 UTC, bearophile wrote:
> Nordlöw:
>
>> I have graph traversal algorithm that needs to keep track of the N "best" node visit.
>
> std.algorithm.topNCopy?
>
> Bye,
> bearophile
Could you please elaborate a bit how you mean this should be used. Notice that the number of visited nodes are in the millions or perhaps even tens of millions. And N is typically 100-1000.
|
March 25, 2015 Re: Keep Track of the Best N Nodes in a Graph Traversal Algorithm | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | On Wednesday, 25 March 2015 at 13:55:29 UTC, bearophile wrote:
> Nordlöw:
>
>> I have graph traversal algorithm that needs to keep track of the N "best" node visit.
>
> std.algorithm.topNCopy?
>
> Bye,
> bearophile
Notice that, ideally, I would like my list of top-nodes to have a fixed size during the whole algorithm (99.9 % of time) as soon it has reached the length of N.
|
March 25, 2015 Re: Keep Track of the Best N Nodes in a Graph Traversal Algorithm | ||||
---|---|---|---|---|
| ||||
Posted in reply to Per Nordlöw | On Wednesday, 25 March 2015 at 14:40:28 UTC, Per Nordlöw wrote:
> On Wednesday, 25 March 2015 at 13:55:29 UTC, bearophile wrote:
>> Nordlöw:
>>
>>> I have graph traversal algorithm that needs to keep track of the N "best" node visit.
>>
>> std.algorithm.topNCopy?
>>
>> Bye,
>> bearophile
>
> Notice that, ideally, I would like my list of top-nodes to have a fixed size during the whole algorithm (99.9 % of time) as soon it has reached the length of N.
What's wrong with binary heaps?
|
March 25, 2015 Re: Keep Track of the Best N Nodes in a Graph Traversal Algorithm | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tobias Pankrath | On Wednesday, 25 March 2015 at 17:49:49 UTC, Tobias Pankrath wrote: > What's wrong with binary heaps? Ahh, a Binary Heap perfectly matches my needs. https://en.wikipedia.org/wiki/Binary_heap http://dlang.org/phobos/std_container_binaryheap.html Thx |
March 25, 2015 Re: Keep Track of the Best N Nodes in a Graph Traversal Algorithm | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | Nordlöw:
> Ahh, a Binary Heap perfectly matches my needs.
>
> https://en.wikipedia.org/wiki/Binary_heap
> http://dlang.org/phobos/std_container_binaryheap.html
But isn't topNCopy using a heap?
Bye,
bearophile
|
Copyright © 1999-2021 by the D Language Foundation