Re: what is the best datatype for..

On Nov 20, 12:56 am, "Hilton" <nos...@xxxxxxxxxx> wrote:

<snip>

Nope, no scanning whatsoever.

If you know you'll have say 1000 possible indices, then define an array of
1000 structs, then when you see a value of 605, you simply do
"array[605].count++" (i.e. your basic histogram code). I bet that is faster
than any dictionary implementation.

That depends on how many samples there are. Suppose there's only one
sample, but a range of size 100,000 - with the dictionary approach,
you'd only have a single entry to sort, whereas with your approach
you'd have to sort 100,000 entries. Which of those do you think would
be quicker?

(Note that using a struct may well be slower than using a class, by
the way - when sorting, each swap would be swapping more data. I
wouldn't like to say without testing though.)

Personally I'd go for the simplest code first and only optimise when
it's shown to be necessary - but at that point I'd definitely be
benchmarking instead of guessing. I would *try* using a Dictionary to
collect the values, then converting it to a list and sorting the list.
That way you wouldn't pay a penalty for unused values, although
there's a higher constant factor due to more copying being involved.

Jon
.

Relevant Pages

  • Re: A Fast sorting algorithm for almost sorted data
    ... far my compressor has potential but is nowhere near ready. ... It does however make heavy use of sorting. ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ...
    (comp.compression)
  • Re: Sorting routine
    ... n RSHIFT shifts n bits. ... in the output array. ... This would be handy for sign sorting of 2's complement. ... So Radix/Distribution sort is about 1.4 times faster than Sedge's Sort. ...
    (comp.lang.forth)
  • Re: Efficiently Extracting Identical Values From A List/Array
    ... struct SortHelper ... Now sort that array according to NodeIndex: ... running through the data structure and sorting things out. ...
    (comp.lang.cpp)
  • Re: indirect sort
    ... I wrote a Comparator (I don't want to use ... Comparable in order to be able to choose the field I am sorting by) ... a way to create a doublearray of my fields I want to sort by, ...
    (comp.lang.java.programmer)
  • Re: sorting by multiple criterias (sub-sorting)
    ... and I want to sort these ... > are multiple records with the same name, sorting this group ... > name and same age, ... Quoting from "How do I sort an array by?" ...
    (comp.lang.perl.misc)