Thread: interesting new container algorithm -- worth the interest?

  1. #1
    Registered User
    Join Date
    May 2004
    Posts
    73

    interesting new container algorithm -- worth the interest?

    Hey guys, I just designed a new container algorithm (think stl::set) and I wanted to know if you all think it looks useful.

    AVL tree (for comparison):
    Inserting in sorted order: O(logn)
    Removing with sorted order: O(logn)
    Finding: O(logn)
    Iterating in sorted order: O(n)

    My algorithm:
    Inserting in sorted order: O(sqrt(n)), but with average time of logn
    Removing with sorted order: O(1)
    Finding: O(1)
    Iterating in sorted order: O(n)

    I think it's really cool, but the O(sqrt(n)) insertion worries me. It would only happen if it was fed something that was already sorted, which I think would be a common case.

    - Evan Ovadia

  2. #2
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    Quote Originally Posted by Verdagon View Post
    Hey guys, I just designed a new container algorithm (think stl::set) and I wanted to know if you all think it looks useful.

    AVL tree (for comparison):
    Inserting in sorted order: O(logn)
    Removing with sorted order: O(logn)
    Finding: O(logn)
    Iterating in sorted order: O(n)

    My algorithm:
    Inserting in sorted order: O(sqrt(n)), but with average time of logn
    Removing with sorted order: O(1)
    Finding: O(1)
    Iterating in sorted order: O(n)

    I think it's really cool, but the O(sqrt(n)) insertion worries me. It would only happen if it was fed something that was already sorted, which I think would be a common case.

    - Evan Ovadia
    I would like to see your proofs of those claims of O(1) for sorting and finding algorithms.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Verdagon
    Hey guys, I just designed a new container algorithm (think stl::set) and I wanted to know if you all think it looks useful.
    I noticed that you posted this in the C++ programming forum, though it is about a general data structure that could be implemented in and for any programming language. To check: you have implemented this in C++, presumably with an interface along the lines of std::set, and want to share it with us?

    Quote Originally Posted by Verdagon
    I think it's really cool, but the O(sqrt(n)) insertion worries me.
    In other words, you cited O(sqrt(n)) as the worst case for insertion? If so, you are also citing O(1) search as the worst case? I agree with nimitzhunter: you really should elaborate.

    Quote Originally Posted by nimitzhunter
    I would like to see your proofs of those claims of O(1) for sorting and finding algorithms.
    Assuming that the claimed properties are correct, you still need n log n time in the average case for sorting since you would be inserting n items with an average case of log n time to insert each item. O(1) for finding is already well known with hash tables, but that is in the average case with a good hash function, not the worst case (plus hash tables are not sorted).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I already know how to make a container with O(sqrt(n)) finding, insertion and removal, and O(n) iteration through them in order, and I bet your idea is very similar.

    You have an array of items and an array of list indexes. The list indexes amount to a linked-list of the items in order, and the array contains the items in random order.
    With insertion you swap a random item to the nth spot and put the new item where that item came from. You also update the list indexes to maintain the list in order.
    With removal you do the swap with last and pop trick, whilst also updating the list indexes.
    For searching you first step through the array over sqrt(n) items finding the lowest item that is lower than the desired item, and then you continue through the list from that point.
    Basically the idea is the heart of the OrderSort algorithm, which is an O(n*sqrt(n)) sorting algorithm.
    Memory usage is O(n).

    Are you sure yours isn't the same thing and you've simply put the Big-Oh notations against the wrong things? Otherwise, care to explain how your claims are possible?

    Note that what I've described is still comparison based. If yours is not comparison based (which I can't see how it could be given O(1) finding), then it isn't anywhere near as generic as a std::set.

    I also know of an algorithm where insertion, find, and removal are O(1), although it assumes a limited range of values, and has something like O((n*k)!) setup time and memory requirements. You create enough arrays to contain every possible state and store a little extra info about which operation takes you to which other state.
    My point being that you also need to state the memory usage.
    Last edited by iMalc; 12-03-2010 at 03:05 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    May 2004
    Posts
    73
    I'm reluctant to post the code because I want to write one of those fancy academic papers first, so I can get credit before I release it. When it's written and released, I'll totally post it here first =D

    Yes, it can be done in any language, I just wrote this one in C++.

    This is distantly related to hash tables, so it has the same removing/finding properties as it. I thought hash tables were constant finding/removal, but you're right, hash tables do have a worst case O(n), huh? It's odd that so many places say its O(1) without mentioning collisions and stuff getting in the way.

    n log n average time for sorting would be correct.

  6. #6
    Registered User
    Join Date
    May 2004
    Posts
    73
    Very interesting reply, I've never heard of this kind of structure. What's it called?

    My structure doesn't sound like what you've explained, but the space requirements for this would would be O(n).

  7. #7
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Inserting in sorted order: O(sqrt(n)), but with average time of logn
    Removing with sorted order: O(1)
    Finding: O(1)
    Iterating in sorted order: O(n)
    space requirements for this would would be O(n)
    O_o

    If by "finding" you mean indexing (i.e. getting the 27 element is O(C)) and by "with average time of logn" you mean "with amortized time of logn" I believe you.

    Otherwise, pick three of the five and call it a day.

    [Edit]
    Oops.

    it has the same removing/finding properties as it
    I missed this.

    Considering what that would mean for your algorithmic complexities, I completely believe you.

    [/Edit]

    Soma

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    What's it called?
    iContainer of course!

    Soma
    Last edited by phantomotap; 12-03-2010 at 07:19 AM. Reason: joke

  9. #9
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by Verdagon View Post
    I'm reluctant to post the code because I want to write one of those fancy academic papers first, so I can get credit before I release it. When it's written and released, I'll totally post it here first =D
    Yes, but then... what's the purpose of this thread if we can't confirm your claims and you can detail them?

    Best if we wait until you can produce the algorithm. I, for one, will be eagerly awaiting.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  10. #10
    Registered User
    Join Date
    May 2004
    Posts
    73
    Okay cool. I was afraid the sqrt(n) insertion would mean that nobody would take it seriously because its slow, but apparently you guys do =D

    I'll make that paper right away!

  11. #11
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by Verdagon View Post
    Okay cool. I was afraid the sqrt(n) insertion would mean that nobody would take it seriously because its slow, but apparently you guys do
    Of course we do! You have to take into consideration structures like these are used in many contexts. For those in which insertion speed is not a variable to take into consideration (either because there's no insertion happening, or it happens in non performance critical areas), sqrt(n) insertion is a non issue.
    Last edited by Mario F.; 12-03-2010 at 03:05 PM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  12. #12
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Verdagon View Post
    Okay cool. I was afraid the sqrt(n) insertion would mean that nobody would take it seriously because its slow, but apparently you guys do =D

    I'll make that paper right away!
    It depends on what it's used for in my opinion. If insertion is a relatively rare solution, this container might still be better than others. But if insertion is more common this might be useless.

    But I agree what has been set before: I doubt your claims, to be honest. See, an O(1) search implies quite a lot...


    Edit: I just had a thought... Are those complexities not dependent on another variable, such as the length of the input. Eg. if we insert strings into it, is the complexity not dependent on the length? If they are, you should add them to the complexity notations. If not, then I doubt the O(1) search worst case a lot...
    Last edited by EVOEx; 12-03-2010 at 03:17 PM.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by EVOEx
    But I agree what has been set before: I doubt your claims, to be honest. See, an O(1) search implies quite a lot...
    I may have misinterpreted the statement, but it seems to me that Verdagon admitted in post #5 that the worst case for search is actually O(n).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by laserlight View Post
    I may have misinterpreted the statement, but it seems to me that Verdagon admitted in post #5 that the worst case for search is actually O(n).
    Hmm that's not how I read that post. But if that is the case, wouldn't it make his container always slower than the AVL tree? I mean, it would only be faster if there would be a large number of removes, but for that you'd need the (slower) insert first.

  15. #15
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    If find is O(n), I don't see how remove can be O(1)
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 03-26-2010, 08:15 AM
  2. please help me with this loop
    By bliznags in forum C Programming
    Replies: 2
    Last Post: 03-21-2005, 08:57 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM