IWETHEY v. 0.3.0 | TODO
1,095 registered users | 0 active users | 0 LpH | Statistics
Login | Create New User
IWETHEY Banner

Welcome to IWETHEY!

IWETHEY Home / IWETHEY Board / Theory and Practice of Programming Forum / That would be a radix-search, I think.
Post #273,974
by static
Picture of static
11/26/06 5:59:13 PM
Reply
New That would be a radix-search, I think.
Ideal for numeric data like SSNs.
"Don't give up!"
Post #274,006
by tuberculosis
Picture of tuberculosis
11/26/06 11:18:48 PM
Reply
New Nah, you want a hash
You always want a hash. O(1) is really hard to beat.


[link|http://www.blackbagops.net|Black Bag Operations Log]

[link|http://www.objectiveclips.com|Artificial Intelligence]

[link|http://www.badpage.info/seaside/html|Scrutinizer]
Post #274,012
by static
Picture of static
11/26/06 11:51:29 PM
Reply
New I thought a radix search was also O(1).
Perhaps I'm misremembering, but a radix-search is very similar to a hash lookup, but uses the value itself directly rather than hashing it first. I think in practice it's a little more complicated than that, but that's the idea.

Wade.
"Don't give up!"
Post #274,028
by tuberculosis
Picture of tuberculosis
11/27/06 12:27:44 AM
Reply
New Gah - my bad
I was thinking of radix sort - which is O(nk) where k is key size.

Search is, as you say, proportional to k or O(1).


[link|http://www.blackbagops.net|Black Bag Operations Log]

[link|http://www.objectiveclips.com|Artificial Intelligence]

[link|http://www.badpage.info/seaside/html|Scrutinizer]
     Steve Yegge (who he? - ed) on Perl - (pwhysall) - (62) - Nov. 25, 2006, 07:28:41 PM EST
         IRLRPD. (new thread) - (Another Scott) - Nov. 25, 2006, 07:54:59 PM EST
         He worked for Amazon for many years - (tuberculosis) - (60) - Nov. 25, 2006, 08:42:36 PM EST
             Well based on that ... - (folkert) - (59) - Nov. 25, 2006, 09:50:54 PM EST
                 Key factors are - (tuberculosis) - (58) - Nov. 25, 2006, 10:08:42 PM EST
                     do it all the time - (boxley) - Nov. 25, 2006, 10:54:26 PM EST
                     I have never had an under spec'd system. - (folkert) - (56) - Nov. 26, 2006, 01:56:19 PM EST
                         More to the point is will it fit on one machine? - (tuberculosis) - (55) - Nov. 26, 2006, 04:44:19 PM EST
                             I guess I think to simply. - (folkert) - (22) - Nov. 26, 2006, 05:09:35 PM EST
                                 You would filewalk for every query? - (crazy) - (18) - Nov. 26, 2006, 05:22:25 PM EST
                                     RAMFS? -NT - (folkert) - (17) - Nov. 26, 2006, 05:34:52 PM EST
                                         Doesn't matter - (crazy) - (5) - Nov. 26, 2006, 05:49:53 PM EST
                                             That would be a radix-search, I think. - (static) - (3) - Nov. 26, 2006, 05:59:13 PM EST
                                                 Nah, you want a hash - (tuberculosis) - (2) - Nov. 26, 2006, 11:18:48 PM EST
                                                     I thought a radix search was also O(1). - (static) - (1) - Nov. 26, 2006, 11:51:29 PM EST
                                                         Gah - my bad - (tuberculosis) - Nov. 27, 2006, 12:27:44 AM EST
                                             Also, I just thought about your file size - (crazy) - Nov. 26, 2006, 06:06:09 PM EST
                                         On a 32 bit machine? -NT - (tuberculosis) - (10) - Nov. 26, 2006, 10:52:50 PM EST
                                             Ever heard of PAE? - (folkert) - (9) - Nov. 26, 2006, 10:56:33 PM EST
                                                 I'd call that exotic technology -NT - (tuberculosis) - (8) - Nov. 26, 2006, 11:11:49 PM EST
                                                     No, it is bone stock on everything since the P3 from Intel - (folkert) - (7) - Nov. 27, 2006, 02:18:48 PM EST
                                                         And AMD? PowerPC? ARM? - (tuberculosis) - (6) - Nov. 27, 2006, 02:30:16 PM EST
                                                             You said COMMON 32-bit - (folkert) - (5) - Nov. 27, 2006, 02:35:31 PM EST
                                                                 That kind of weasel won't get you a job - (tuberculosis) - (4) - Nov. 27, 2006, 02:35:03 PM EST
                                                                     This line of questioning wouldn't get you a candidate for - (folkert) - (3) - Nov. 27, 2006, 02:36:54 PM EST
                                                                         Whoa - (crazy) - (2) - Nov. 27, 2006, 02:43:30 PM EST
                                                                             No he got downright rude. -NT - (folkert) - (1) - Nov. 27, 2006, 02:47:43 PM EST
                                                                                 I'm not trying to be rude - (tuberculosis) - Nov. 27, 2006, 03:48:04 PM EST
                                 Where did you get 1G? - (tuberculosis) - (2) - Nov. 26, 2006, 10:50:05 PM EST
                                     Not all 9 digit numbers are valid. - (Another Scott) - (1) - Nov. 26, 2006, 11:08:48 PM EST
                                         I assumed so - (tuberculosis) - Nov. 26, 2006, 11:15:44 PM EST
                             something you forgot, what lawyer to hire - (boxley) - (1) - Nov. 26, 2006, 05:40:12 PM EST
                                 Nah - (crazy) - Nov. 26, 2006, 05:51:36 PM EST
                             We talked about this one before - (admin) - (6) - Nov. 26, 2006, 10:14:49 PM EST
                                 We did - he didn't - (tuberculosis) - (5) - Nov. 26, 2006, 11:06:33 PM EST
                                     Just saying... - (admin) - (4) - Nov. 26, 2006, 11:14:33 PM EST
                                         But we hardly talk about programming at all anymore - (tuberculosis) - (3) - Nov. 26, 2006, 11:18:18 PM EST
                                             :-) - (Another Scott) - (2) - Nov. 26, 2006, 11:42:56 PM EST
                                                 I agree on the eyeballs. - (static) - Nov. 26, 2006, 11:59:12 PM EST
                                                 I put most of my programming rants on my blog - (tuberculosis) - Nov. 27, 2006, 12:26:11 AM EST
                             non programmer answer, append a 0,1 or2 - (boxley) - (15) - Nov. 27, 2006, 05:45:45 PM EST
                                 PICK?!?!?!?!?!?!?!?!?!?!? - (crazy) - (5) - Nov. 27, 2006, 06:40:21 PM EST
                                     dont knock it until you have tried it, recently -NT - (boxley) - (4) - Nov. 27, 2006, 07:58:22 PM EST
                                         I've spent the last 20 years systematically killing it - (crazy) - (3) - Nov. 27, 2006, 09:06:38 PM EST
                                             again, see what the needs are and then ask what the solution - (boxley) - (2) - Nov. 27, 2006, 10:58:55 PM EST
                                                 One trick pony - (crazy) - (1) - Nov. 27, 2006, 11:06:48 PM EST
                                                     If that is the trick you need use it -NT - (boxley) - Nov. 28, 2006, 06:59:22 AM EST
                                 The key is to stay off the disk - (tuberculosis) - (8) - Nov. 27, 2006, 06:44:04 PM EST
                                     CramFS in RAM. -NT - (folkert) - (6) - Nov. 27, 2006, 07:27:32 PM EST
                                         That's not a solution either - (tuberculosis) - (5) - Nov. 27, 2006, 08:14:50 PM EST
                                             Okay, at this point... - (folkert) - (4) - Nov. 27, 2006, 09:45:49 PM EST
                                                 Sure - just want to give you a taste - (tuberculosis) - (3) - Nov. 27, 2006, 10:58:48 PM EST
                                                     personally I hate programming, I like debugging - (boxley) - Nov. 27, 2006, 11:05:54 PM EST
                                                     Cheaper at Bookpool, btw. - (admin) - Nov. 27, 2006, 11:15:28 PM EST
                                                     ICLRPD - (drewk) - Nov. 27, 2006, 11:39:45 PM EST
                                     Math isnt my strong suit but - (boxley) - Nov. 27, 2006, 08:25:07 PM EST
                             I hope you're going to outline the solution. :-) - (Another Scott) - (3) - Nov. 27, 2006, 09:33:15 PM EST
                                 Admin did it very nicely. - (crazy) - (1) - Nov. 27, 2006, 09:49:53 PM EST
                                     D'Oh! Thanks. -NT - (Another Scott) - Nov. 27, 2006, 09:58:57 PM EST
                                 Cool sort paper - (crazy) - Nov. 27, 2006, 09:55:50 PM EST
                             Taking a stab - (ChrisR) - (2) - Nov. 27, 2006, 10:07:24 PM EST
                                 Still doesn't beat O(1) :-) -NT - (admin) - (1) - Nov. 27, 2006, 10:13:27 PM EST
                                     Ok, I read the answer you gave... - (ChrisR) - Nov. 27, 2006, 10:19:51 PM EST

Anything that ugly should die and be eaten at breakfast.
225 ms