Topk feature request

[gitboy16]

Hi,
Thanks for the package. Would it be possible to have the ability to return the index of the values instead of the values when using topk?
Thanks

[sl-solution]

Yes, we can add a new function, it should be straightforward. Probably we can call the new function topkperm(?)

[giantmoa]

It would be better to add an extra argument to topk, wouldn't be?

[gitboy16]

It is really up to you, I don't mind an extra argument or a new function as long as it is efficient and as fast as topk. Thank you.

[sl-solution]

I have added the new functionality to the master branch.

topk(x, k; rev = false, output_indices = false)

Return upto k largest nonmissing elements of x. When rev = true it returns upto k smallest nonmissing elements of x. When all elements are missing, the function returns [missing].

If output_indices = true, the function returns the values and their indices.

The topk function uses < for comparing values

[gitboy16]

Thank you. I will have a look on Monday.

[gitboy16]

What I feared happened. topk is now 2 times slower in my benchmark.

x = rand(8*(10^8));
@time InMemoryDatasets.topk(x, 6)
  2.618424 seconds (1 allocation: 112 bytes)

Before I had it at 1.237111 seconds.

[sl-solution]

What I feared happened. topk is now 2 times slower in my benchmark.

x = rand(8*(10^8));
@time InMemoryDatasets.topk(x, 6)
  2.618424 seconds (1 allocation: 112 bytes)

Before I had it at 1.237111 seconds.

I am fixing this. I am also going to go with topkperm, since adding extra keyword argument would cause inference problem.

[sl-solution]

check master.

[gitboy16]

Hi, thank you. I think you have a performance regression issue on topk. On master topk seems slower. 1.754926 seconds (2 allocations: 224 bytes) . It was just 1 allocation before. Did you change topk? On master topk and topkperm seem to have the same performance.

[sl-solution]

On master topk seems slower. 1.754926 seconds (2 allocations: 224 bytes) . It was just 1 allocation before. Did you change topk? On master topk and topkperm seem to have the same performance.

This is expected, since topk now supports any DataType (previously it only supported numeric values) plus the compiler can infer its output correctly (this is important for combine, modify, etc. ). One extra allocation is due to calling allowmissing on the output.

[sl-solution]

Hi, thank you. I think you have a performance regression issue on topk. On master topk seems slower. 1.754926 seconds (2 allocations: 224 bytes) . It was just 1 allocation before. Did you change topk? On master topk and topkperm seem to have the same performance.

Would you please check the improve_topk branch? It still will be 2 allocations, however, it should be much faster and additionally supports two extra keyword arguments: lt and by.

[gitboy16]

Hi, thanks, (using the same benchmark as above) yes topk is a bit faster at 1.65sec and topkperm much faster at 1.35 sec. Thank you

[sl-solution]

Hi, thanks, (using the same benchmark as above) yes topk is a bit faster at 1.65sec and topkperm much faster at 1.35 sec. Thank you

Both should be about the same timing - I guess the difference here is due to something else.

One more thing...

The latest commit adds multithreading to topk and topkperm. check it out and pass threads=true to have a sneak peek.

[gitboy16]

Nice work! Yes I see that both functions have similar performance now but I only see a difference for topk when using multithreading. It doea not seem to work for topkperm. Do you have a private email I can contact you on? Thank you.

[sl-solution]

Nice work! Yes I see that both functions have similar performance now but I only see a difference for topk when using multithreading. It doea not seem to work for topkperm. Do you have a private email I can contact you on? Thank you.

It should be a bug, I am working on that.
You can use my github email directly github.sl.solution@icloud.com.

[sl-solution]

Currently we pass < as the default value for lt, however, in new release we will set isless as the default value for lt. This is because < is not safe when data contains NaN. Thus, to gain the maximum performance, you should pass lt = < when it is suitable.