4 Replies - 3530 Views - Last Post: 11 January 2012 - 01:29 PM

#1 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,710
  • Joined: 03-August 09

Wikipedia wrong about finger trees?

Posted 10 January 2012 - 02:51 PM

so I was reading about finger trees and was shocked to read on Wikipedia(from this link) that constant time random access was possible with finger trees. I looked up a number of implementations and other documents(including those sited in the page) but I was unable to confirm this.

the Wikipedia page said...

Quote

...A finger tree gives amortized constant time access to the "fingers" (leaves) of the tree, where data is stored...


but this says...

Quote

...supporting access to the ends in amortized constant time...


Looking at Haskell's Data.Sequence documentation on hackage it would appear that access time is O(log(min(n, n-i))) which is quite good but it's not constant.

Is this Wikipedia article incorrect? It sure appears to be that to me way but I don't know enough about the subject to say one way or the other.

Is This A Good Question/Topic? 0
  • +

Replies To: Wikipedia wrong about finger trees?

#2 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 9572
  • View blog
  • Posts: 36,243
  • Joined: 12-June 08

Re: Wikipedia wrong about finger trees?

Posted 10 January 2012 - 03:09 PM

First, and I have to get this out of my system, I too am shocked.. YES SHOCKED that wikipedia might be wrong.

Second, aren't you comparing apples to apples with more stuff? You are comparing the "amortized constant" to access time... (amortizing considers all the operators not just one). So you are comparing one operation to the collective whole of all the operations.
Was This Post Helpful? 0
  • +
  • -

#3 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,710
  • Joined: 03-August 09

Re: Wikipedia wrong about finger trees?

Posted 10 January 2012 - 04:27 PM

1) ya, I know Wikipedia isn't the worlds most reliable source so if I see something fishy I check it out. I would also love to find out that such a thing is possible but the evidence for it seems to be lacking and it goes against my intuitions.

2) everything I've read has explicitly stated that it uses amortized time so It should all be kosher to compare.
Was This Post Helpful? 0
  • +
  • -

#4 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Re: Wikipedia wrong about finger trees?

Posted 11 January 2012 - 11:47 AM

Read amortized as "on average". Sometime it takes a little longer, other time it takes a little less.
Was This Post Helpful? 0
  • +
  • -

#5 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,710
  • Joined: 03-August 09

Re: Wikipedia wrong about finger trees?

Posted 11 January 2012 - 01:29 PM

I'm pretty sure I understand what amortized time is. for instance if a dynamic array reallocates every power of 2(to the next power of 2) you can achieve constant amortized push/pop time. each push/pop takes O(1) but then every 'n' pushes it takes O(n) to reallocate an copy the array; because it only happens every 'n' times you get O(1 + n/n) which reduces to O(2) and thanks to the magic of big O notation you get O(1)(e.g. constant). right?

everything I have read about finger trees only says that it offers constant(amortized) access times to the front and back(which makes sense) but nothing other that that page has said that constant access time is possible to all the leafs(possibly something with laziness might make it possible but I don't see how). of course I haven't found explicitly anything denying amortized constant access time for finger trees either.

This post has been edited by ishkabible: 11 January 2012 - 01:30 PM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1