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).
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