interesting new container algorithm -- worth the interest?

This is a discussion on interesting new container algorithm -- worth the interest? within the Tech Board forums, part of the Community Boards category; Originally Posted by Mario F. If find is O(n), I don't see how remove can be O(1) Depends on how ...

  1. #16
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    Quote Originally Posted by Mario F. View Post
    If find is O(n), I don't see how remove can be O(1)
    Depends on how you define remove. It could be "remove given a pointer to the element you want removed".

  2. #17
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,172
    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?
    This seems a quality of implementation issue, but I'm not entirely sure I understand what you are asking.

    But if that is the case, wouldn't it make his container always slower than the AVL tree?
    No. A hash table implementation with even simplified amortized constant time operations could easily outperform an AVL tree if the use case implies rare mutation after an initial setup phase. It could also be the case that the AVL tree would be faster in the very same scenario if the comparison of objects is cheap while hashing those objects would be expensive or impossible to plan (user generated strings of widely varying length and content).

    *shrug*

    It could also be the case that a B*tree would be the fastest option. It really depends on what you are doing and not on what academic "Big O" operations a data structure may have.

    If find is O(n), I don't see how remove can be O(1)
    He said both operations are related to the expectations for hash tables.

    Soma

  3. #18
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,172
    It could be "remove given a pointer to the element you want removed".
    That doesn't really change the nature of the statement.

    Removing an element of a singly linked list even when given an iterator is still an "O(n)" operation.

    The relationship is going to depend on the data structure and the underlying implementation.

    Soma

  4. #19
    Registered User
    Join Date
    May 2004
    Posts
    73
    I've learned from various places that hash tables have O(1) finding time, and this is a common misconception apparently. Hash tables are O(n), which means my container is O(n).

    Cyberfish is right, once an element is found in my container, removing it is indeed O(1), it's one of the weird properties of my container but this is true. If you consider the removal operation to include finding the element first, then it's O(n), but there's other ways to get an iterator than by searching for it.

  5. #20
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,635
    Hash tables are only O(n) when they need to find an element due to collisions at some subscript or otherwise. With perfect hashing look up in O(1) time is assured, but in general you should choose a hashing algorithm that is close enough to O(1) results anyway; since most published algorithms pass the avelanche test.

    The weird thing about what you've talked about is that you haven't really described the container at all and you only state that it has so many properties. That's great.

  6. #21
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    Keep in mind your algorithm and container need serious peer review to validate the claims you are making about it. This would be a 'kind' place to get such a review. The members who have answered you thus far in this thread are very intelligent programmers and computer scientists. You would do well to listen to them and allow them to review your algorithm.

    My thinking is you won't allow any of them to review it b/c you know deep down they might find fault with it. I wouldn't worry about that b/c it would be better to find fault with it or perhaps validate it now than later. If you are so sure that it is a great container then you should not be concerned about allowing people to see it. If you are concerned with people stealing it then put a copyright on the code and/or use an open-source type license and then allow people to review it. Honestly no one here is going to steal your code or your idea. I'm a firm believer that there are not that many 'original' algorithms or containers left to be built so I'm anxious to see you disprove that.
    Last edited by VirtualAce; 12-04-2010 at 09:08 PM.

  7. #22
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    Quote Originally Posted by Verdagon View Post
    Cyberfish is right, once an element is found in my container, removing it is indeed O(1),
    That's expected.

    Quote Originally Posted by Verdagon View Post
    it's one of the weird properties of my container but this is true. If you consider the removal operation to include finding the element first, then it's O(n),
    Being that the case, that's the one that matters on a worst case scenario, which is the whole point of the Big O notation. Otherwise, if you feel like pointing out there's best case scenario, you need to separate deleting operations into the two realities.

    Quote Originally Posted by Verdagon View Post
    but there's other ways to get an iterator than by searching for it.
    Since we know now search is O(n), I dare not ask
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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.

  8. #23
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Bubba View Post
    My thinking is you won't allow any of them to review it b/c you know deep down they might find fault with it. I wouldn't worry about that b/c it would be better to find fault with it or perhaps validate it now than later.
    Exactly. How about that guy that went public finding a time traveller in some old movie (charlie chaplin or so, heck I'm too young for this), because a person would be speaking on a mobile phone. It was pointed out quite quickly on slashdot that the device was in fact (likely) a hearing aid of that time, not a mobile phone. Boy, must that guy have felt stupid.

    Anyways, phantomotap, yes I understand the container might still be useful if we're talking strictly about worst case. We need average case to be able to tell anything about this container, but it sounds like he simply reinvented hashtables. In that case, his original comparison with the AVL tree is completely useless. It's like: "Look, I'm way faster than this specific container in worst case", only to move onto "Okay, that container is better in worst case". I am not going to compare it with other containers than he did in other cases (average, for instance) just because his original comparison was wrong.

    About the "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?" you didn't understand: I was thinking tries, where the complexity is independent of the number of elements in the container. I thought he may have used a similar idea, but missed out on the length, even though it was important, in the complexities.

    So, Verdagon, you've made a few wrong claims already. If you want to be taken serious about this still you'll have to show some proof. At least make a new comparison; show us the average case of your container vs. hash tables.

    Mario F., O(1) removal is not always the case in containers, when the iterator is known: trees might have to be re-balanced, all the elements in an array may have to be shifted left one field, etc.
    Last edited by EVOEx; 12-05-2010 at 03:55 AM.

  9. #24
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    Quote Originally Posted by EVOEx View Post
    Mario F., O(1) removal is not always the case in containers, when the iterator is known: trees might have to be re-balanced, all the elements in an array may have to be shifted left one field, etc.
    It is the accepted result for hash table lookup (you certainly agree we cannot contemplate those factors when describing our algorithm in Big-O). But honestly I don't know anymore what type of container the OP is talking about -- If said container exists at all.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    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. #25
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,172
    I'm a firm believer that there are not that many 'original' algorithms or containers left to be built so I'm anxious to see you disprove that.
    That's me, but you never know when someone might manage something great even if it is just a variation on a theme.

    I was thinking tries, where the complexity is independent of the number of elements in the container.
    I see. When he said that about his container being related to hash tables I dismissed everything other than a hash table with a unique schedule using a B+Tree for the bins.

    Soma

  11. #26
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by phantomotap View Post
    I see. When he said that about his container being related to hash tables I dismissed everything other than a hash table with a unique schedule using a B+Tree for the bins.
    Well, dismissing types of containers doesn't go too well in this thread :P. To me, it sounds like a hoax (or, more likely, a mistake).

    I agree with Mario ;-).

    Bring on the container. Until that time, I consider it non-existant.

Page 2 of 2 FirstFirst 12
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, 07: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21