You would filewalk for every query?

Post #273,966 by crazy 11/26/06 5:22:25 PM Reply	You would filewalk for every query? What is the worst case for a single transaction? If you had 500 hit within 2 seconds, how many will you be able to satisfy before a person gets annoyed and presses cancel? How about 5,000? Keep going. Basically, simple may be OK for a single activity, but it rarely scales, at least cost-effectively.
Post #273,970 by folkert 11/26/06 5:34:52 PM Reply	RAMFS? -- [link\|mailto:greg@gregfolkert.net\|greg], [link\|http://www.iwethey.org/ed_curry\|REMEMBER ED CURRY!] @ *i_wethey* Freedom is not FREE. Yeah, but 10s of Trillions of US Dollars? SELECT * FROM scog WHERE ethics > 0; 0 rows returned.
Post #273,972 by crazy 11/26/06 5:49:53 PM Reply	Doesn't matter You've got to go through each bottleneck during an access and then see where people start piling up. How fast can a program read a file, even if it is pure ram disk. Hmm - I seem to recall moving data at 300MB per second when walking through a fully cached 1GB file on an Opteron - so let's say if you average out finding stuff in 1/2 the time, ie: 1.5 seconds for that piece of the puzzle. So, you can server 6 or 7 queries in about 10 seconds, which is what I consider an absolute, worst case, will not wait any longer until I hit the STOP button. But it is really a waste of activity anyway. So then your choice is to start working through access and storage. It is preferable if you can code a single program to load the data in memory, and this program has very quick access to the data, and then this program can publish a server interface (simple tcp/ip socket, etc), which other programs can use. And then you think in terms of memory usage. You don't really need to actually store the data if you can come up with a representation of existence. You'd rather use less resources if possible, as long as it doesn't slow down your access. I seem to recall this particular task lends itself to bitmapped scoreboarding. Also, which a bit of knowledge of the data type, I seem to recall only certain ranges of numbers are used. So when you end up compressing what you store, and add a bit of smarts to the search method, you go from serving a couple of dozen query a minute to a couple of thousand a second. At that point you find your networking socket creation becomes the bottleneck, rather than the actual query, so then you might move tho optimizing that. Or you may find a couple of cheap load balanced machines takes care of your complete universe of possible usage, so you stop.
Post #273,974 by static 11/26/06 5:59:13 PM Reply	That would be a radix-search, I think. Ideal for numeric data like SSNs. "Don't give up!"
Post #274,006 by tuberculosis 11/26/06 11:18:48 PM Reply	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 11/26/06 11:51:29 PM Reply	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 11/27/06 12:27:44 AM Reply	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]
Post #273,976 by crazy 11/26/06 6:06:09 PM Reply	Also, I just thought about your file size It is a LOT worse than what you thought if you actually have each number, so our initial query time for a filewalk just jumped tremendously.
Post #273,998 by tuberculosis 11/26/06 10:52:50 PM Reply	On a 32 bit machine? [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 #273,999 by folkert 11/26/06 10:56:33 PM Reply	Ever heard of PAE? It has been a part of Intel 32-bit for a LONG time. -- [link\|mailto:greg@gregfolkert.net\|greg], [link\|http://www.iwethey.org/ed_curry\|REMEMBER ED CURRY!] @ *i_wethey* Freedom is not FREE. Yeah, but 10s of Trillions of US Dollars? SELECT * FROM scog WHERE ethics > 0; 0 rows returned.
Post #274,001 by tuberculosis 11/26/06 11:11:49 PM Reply	I'd call that exotic technology [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,072 by folkert 11/27/06 2:18:48 PM Reply	No, it is bone stock on everything since the P3 from Intel The most support Chipset supports PAE, except most MB manufacturers didn't enable it. -- [link\|mailto:greg@gregfolkert.net\|greg], [link\|http://www.iwethey.org/ed_curry\|REMEMBER ED CURRY!] @ *i_wethey* Freedom is not FREE. Yeah, but 10s of Trillions of US Dollars? SELECT * FROM scog WHERE ethics > 0; 0 rows returned.
Post #274,076 by tuberculosis 11/27/06 2:30:16 PM Reply	And AMD? PowerPC? ARM? >most MB manufacturers didn't enable it. So it would be a bad idea to count on it I think. There's a lot more reasons I'd discount this solution. For one - the problem says a 32 bit machine. It doesn't say a 32 bit Intel machine. It doesn't say a 36 bit machine - which is essentially what PAE gives you if its enabled. It says - a vanilla 32 bit machine. I'm not saying PAE is bad. I'm not saying it isn't widely available. I'm saying it is outside of the problem definition. [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,077 by folkert 11/27/06 2:33:06 PM 11/27/06 2:35:31 PM Reply	You said COMMON 32-bit Power,ARM even AMD are also outside the problems definition. Edit: Excuse me, "garden variety 32 bit" Garden Variety... Doesn't mean exotics like Power, ARM, MIPS, MIPS-EL, SH, s390 or even AMD. -- [link\|mailto:greg@gregfolkert.net\|greg], [link\|http://www.iwethey.org/ed_curry\|REMEMBER ED CURRY!] @ *i_wethey* Freedom is not FREE. Yeah, but 10s of Trillions of US Dollars? SELECT * FROM scog WHERE ethics > 0; 0 rows returned. Edited by folkert Nov. 27, 2006, 02:35:31 PM EST Expand All History
Post #274,078 by tuberculosis 11/27/06 2:33:49 PM 11/27/06 2:35:03 PM Reply	That kind of weasel won't get you a job And I said 'garden variety' [link\|http://www.blackbagops.net\|Black Bag Operations Log] [link\|http://www.objectiveclips.com\|Artificial Intelligence] [link\|http://www.badpage.info/seaside/html\|Scrutinizer] Edited by tuberculosis Nov. 27, 2006, 02:35:03 PM EST Expand All History
Post #274,079 by folkert 11/27/06 2:36:54 PM Reply	This line of questioning wouldn't get you a candidate for the job in the first place. You knocked out many worth while one even before you stop to consider you rant. -- [link\|mailto:greg@gregfolkert.net\|greg], [link\|http://www.iwethey.org/ed_curry\|REMEMBER ED CURRY!] @ *i_wethey* Freedom is not FREE. Yeah, but 10s of Trillions of US Dollars? SELECT * FROM scog WHERE ethics > 0; 0 rows returned.
Post #274,080 by crazy 11/27/06 2:43:30 PM Reply	Whoa The key issue was guiding you toward a reasonable doable solution, at least to get you thinking along those lines. But since you really don't have the programming background, you attempted a brute force response (which is typical for non-programmers) and then got upset when he refocused. There is absolutely NO WAY your anticipated solution would have been workable, even with all the memory available in PAE. Didn't matter. So he pointed you back to the simple original requirements. But rather than take the direction, you got silly.
Post #274,081 by folkert 11/27/06 2:47:43 PM Reply	No he got downright rude. -- [link\|mailto:greg@gregfolkert.net\|greg], [link\|http://www.iwethey.org/ed_curry\|REMEMBER ED CURRY!] @ *i_wethey* Freedom is not FREE. Yeah, but 10s of Trillions of US Dollars? SELECT * FROM scog WHERE ethics > 0; 0 rows returned.
Post #274,095 by tuberculosis 11/27/06 3:48:04 PM Reply	I'm not trying to be rude I'm trying to help you. When I say PAE is out of bounds - accept it and try a new avenue. Don't spend time defending it as a choice. Your interviewer has specific things he wants to see. This is no different than asking you to reverse a string, watching you allocate space for a new one, and then me refocusing to say "OK - but the string is ginormous and there is no more memory available - now what will you do". Because I want to see the in-place solution. You said you want to be a programmer. I'm happy to help you achieve that and coach you through what passes as interviewing these days. The really-hard-puzzle-solve-this-on-the-spot interview is very popular now. [link\|http://www.blackbagops.net\|Black Bag Operations Log] [link\|http://www.objectiveclips.com\|Artificial Intelligence] [link\|http://www.badpage.info/seaside/html\|Scrutinizer]

Welcome to IWETHEY!