Building data structures that are smaller than an array and faster (in C)

Re:Building data structures that are smaller than an array a... by tabbyjabby on Wednesday February 29, 2012 @11:32PM (#3650918)

Bit confused here --

The author rewrites the initial values as:

1 0 2 0 2 3

He defines the keys array as:

2 3 4 6

Using the method defined in the article to find the values of each of the elements of the rewritten array, wouldn't the values be:

3 2 4 2 4 6

which does not equal the original values of:

3 2 4 6 2 6

[ Parent | on HN ]

Re:Building data structures that are smaller than an array a... by siganakis on Thursday March 01, 2012 @12:23AM (#3651042)

My bad, I got that wrong.

The translated array should be:

1 0 2 3 0 3.

I am correcting the article now. For a non-rushed, accurate description please look at:

http://www.alexbowe.com/wavelet-trees

Edit: Got it wrong again... I guess this is why we have computers and debuggers!

[ Parent | on HN ]

Re:Building data structures that are smaller than an array a... by amatus on Thursday March 01, 2012 @11:55AM (#3652877)

Looks like you still have some bugs:

  rewritten data: 1 0 2 3 0 3
  first row     : 0 0 1 1 0 1
  group a       : 1 0     1
  group b       :     2 2   3

Group a and group b don't seem to match up with the data. Or I've misunderstood something.

[ Parent | on HN ]

Re:Building data structures that are smaller than an array a... by foamboarder on Friday March 02, 2012 @01:18PM (#3657630)

I'm in the same boat. siganakis?

[ Parent | on HN ]

Re:Building data structures that are smaller than an array a... by strags on Wednesday February 29, 2012 @11:45PM (#3650959)

Yeah... I'm a bit confused there too. It's not the clearest article out there.

[ Parent | on HN ]

Re:Building data structures that are smaller than an array a... by tabbyjabby on Wednesday February 29, 2012 @11:50PM (#3650966)

I'm inclined to believe this is an error. I have wasted hours trying to figure something out in a textbook, before I decide to check the errors section and discover that it was just a misprint.

[ Parent | on HN ]