2012-05-10T00:07:28 *** replore_ has quit IRC (Remote host closed the connection) 2012-05-10T00:19:38 *** dvladim has quit IRC (Read error: Operation timed out) 2012-05-10T00:30:01 *** Fandekasp has quit IRC (Ping timeout: 260 seconds) 2012-05-10T00:56:24 *** amstan has quit IRC (Quit: Konversation terminated!) 2012-05-10T00:59:45 *** delt0r has quit IRC (Ping timeout: 245 seconds) 2012-05-10T01:12:33 *** delt0r has joined #aichallenge 2012-05-10T01:20:55 *** Areks has joined #aichallenge 2012-05-10T01:23:24 *** Fandekasp has joined #aichallenge 2012-05-10T02:32:32 *** Jak_o_Shadows has joined #aichallenge 2012-05-10T02:47:14 *** coeus has joined #aichallenge 2012-05-10T02:52:51 *** epicmonkey has joined #aichallenge 2012-05-10T03:16:31 *** coeus has quit IRC (Ping timeout: 248 seconds) 2012-05-10T03:27:54 *** Fandekasp has quit IRC (Remote host closed the connection) 2012-05-10T03:34:54 *** Fandekasp has joined #aichallenge 2012-05-10T03:44:49 *** aerique has joined #aichallenge 2012-05-10T03:45:07 *** epicmonkey has quit IRC (Ping timeout: 256 seconds) 2012-05-10T03:52:12 *** mviel_ has joined #aichallenge 2012-05-10T03:52:31 *** aerique has quit IRC (Quit: ...) 2012-05-10T03:53:33 *** aerique has joined #aichallenge 2012-05-10T03:56:53 *** aerique_ has joined #aichallenge 2012-05-10T03:57:03 *** aerique__ has joined #aichallenge 2012-05-10T03:59:31 *** aerique has quit IRC (Quit: leaving) 2012-05-10T03:59:40 *** aerique_ has quit IRC (Client Quit) 2012-05-10T04:03:43 *** Fandekasp has quit IRC (Remote host closed the connection) 2012-05-10T04:05:39 *** aerique has joined #aichallenge 2012-05-10T04:18:22 *** Fandekasp has joined #aichallenge 2012-05-10T04:57:04 *** epicmonkey has joined #aichallenge 2012-05-10T04:57:28 *** kurnevsky has joined #aichallenge 2012-05-10T05:08:58 *** Jak_o_Shadows has quit IRC (Read error: Connection reset by peer) 2012-05-10T05:19:01 *** cyphase has quit IRC (Read error: Connection reset by peer) 2012-05-10T05:28:54 *** cyphase has joined #aichallenge 2012-05-10T05:30:41 *** Fandekasp has quit IRC (Quit: leaving) 2012-05-10T05:46:13 *** kurnevsky has quit IRC (Quit: Leaving.) 2012-05-10T06:05:39 *** Fandekasp has joined #aichallenge 2012-05-10T06:13:31 *** fggbfdgrt has joined #aichallenge 2012-05-10T06:13:47 *** fggbfdgrt has left #aichallenge 2012-05-10T06:14:27 *** mceier has joined #aichallenge 2012-05-10T06:16:10 *** sigh has joined #aichallenge 2012-05-10T07:29:54 *** Fandekasp has quit IRC (Ping timeout: 252 seconds) 2012-05-10T07:39:04 *** foRei has joined #aichallenge 2012-05-10T08:56:32 *** pairofdice has joined #aichallenge 2012-05-10T09:00:05 *** delt0r has quit IRC (Ping timeout: 244 seconds) 2012-05-10T09:04:17 *** Palmik has joined #aichallenge 2012-05-10T09:04:40 *** amstan has joined #aichallenge 2012-05-10T09:04:40 *** ChanServ sets mode: +o amstan 2012-05-10T09:04:51 *** coeus has joined #aichallenge 2012-05-10T09:06:36 *** mcstar has joined #aichallenge 2012-05-10T09:08:04 how mediocre, i made a prefix trie too 2012-05-10T09:11:33 mcstar: why won't this chip talk to me back? 2012-05-10T09:11:50 ask her nicely 2012-05-10T09:12:01 what kinda chip? 2012-05-10T09:12:07 bma180 2012-05-10T09:12:13 it's an accelerometer 2012-05-10T09:12:19 right.. 2012-05-10T09:12:22 i can ask #sparkfun 2012-05-10T09:13:09 what are you doing with it? 2012-05-10T09:13:25 i want to get acceleration 2012-05-10T09:13:33 yeah i get it, but what for? 2012-05-10T09:13:38 robotics? 2012-05-10T09:13:40 *** delt0r has joined #aichallenge 2012-05-10T09:15:01 idk, for another department 2012-05-10T09:15:29 that's a lot of missiles! http://nationalpostnews.files.wordpress.com/2012/05/fo0505_nuclearweaponsw25001.gif 2012-05-10T09:16:54 im sure the missiles are not to scale 2012-05-10T09:18:48 the ones on the outside are bunched up, so there's even more of them 2012-05-10T09:21:29 hm 2012-05-10T09:21:36 it is not exactly slow 2012-05-10T09:22:11 2.4M file of words, checked every word in couple of minutes in the interpreter 2012-05-10T09:22:26 (compiled to bytecode) 2012-05-10T09:22:41 minutes->seconds 2012-05-10T09:22:47 fail 2012-05-10T09:22:59 mleise: are you there? 2012-05-10T09:23:09 couple of seconds for 2.4M, that seems right 2012-05-10T09:23:17 if you're doing O(n) searches for each word 2012-05-10T09:23:35 mcstar: yes, I'm here 2012-05-10T09:23:47 mleise: you did a prefix tree some time ago right? 2012-05-10T09:24:08 trie 2012-05-10T09:24:47 yes I did. A pretty simple one 2012-05-10T09:24:59 http://hpaste.org/68330 2012-05-10T09:25:09 this is fully immutable/functional 2012-05-10T09:25:15 this is a simple one too 2012-05-10T09:25:39 i found a problem, which is solved with the help of a prefix tree, so i thought id do one 2012-05-10T09:27:22 mleise: can you paster yours? 2012-05-10T09:27:24 -r 2012-05-10T09:31:18 k one moment.... 2012-05-10T09:32:09 http://codepad.org/C1OAhXD6 2012-05-10T09:32:35 It has grown some features like returning the length of a match in addition to the data, or reverse lookups 2012-05-10T09:34:35 mleise: there is not much point in measuring lookup performance 2012-05-10T09:34:54 i mean that ofc should be fast 2012-05-10T09:35:05 but you need to consider allocations 2012-05-10T09:35:29 maybe a repreted fill-up test would be better 2012-05-10T09:35:34 repated* 2012-05-10T09:35:36 f 2012-05-10T09:35:59 mcstar: ok, i have to admit, that my tree was used as a 'constant' 2012-05-10T09:36:22 For a parser I filled it up once at program launch and then only read it 2012-05-10T09:37:07 i fear it will beat hands down my immutable one 2012-05-10T09:37:09 It allocates 256 * pointer_size + data_size for every node 2012-05-10T09:37:15 too bad i cant test your code 2012-05-10T09:37:21 wait, i can 2012-05-10T09:38:34 are you busy? 2012-05-10T09:39:03 (damn, i shouldnt be doing this, but now im curious about a benchmark) 2012-05-10T09:39:42 i dont even know how to read some file in in D :S 2012-05-10T09:41:04 why cant you program in some proper language 2012-05-10T09:49:51 mcstar: Now I am not busy any more 2012-05-10T09:49:58 great 2012-05-10T09:51:39 you can just "read(file);" 2012-05-10T09:53:02 that would be an array of bytes 2012-05-10T09:54:12 how about while(line=file.getline()){} 2012-05-10T09:56:21 ok that would be: auto f = File("filename.txt"); foreach (ref line; f.byLine()) { writeln(line); } 2012-05-10T09:56:54 (file closed when the scope exits) 2012-05-10T09:58:15 mleise: how does a main look like? 2012-05-10T09:58:25 wait, ill check your asteroids 2012-05-10T09:58:31 depends on how much you need: void main() {} 2012-05-10T09:58:54 up to int main(string[]) { return 0; } 2012-05-10T09:59:09 int main(string[] args) { return 0; } 2012-05-10T09:59:44 mleise: ok, and now some timer code 2012-05-10T09:59:50 XD 2012-05-10T10:00:05 well there is "benchmark" in std.datetime 2012-05-10T10:00:15 it times a parameterless function 2012-05-10T10:00:23 or two or three ... 2012-05-10T10:02:35 auto results = benchmark!(foo, bar)(1_000_000); // 1 million calls 2012-05-10T10:02:35 writefln("foo() took: %s ms", results[0].msecs); 2012-05-10T10:02:35 writefln("bar() took: %s ms", results[1].msecs); 2012-05-10T10:02:51 mcstar: ^ 2012-05-10T10:02:53 import std.datetime? 2012-05-10T10:02:56 yes 2012-05-10T10:04:08 mleise: now i need to create your Trie and insert elements 2012-05-10T10:06:42 i guess your trie works for 'string' ? 2012-05-10T10:06:56 yes. the key is always a string 2012-05-10T10:07:05 and the data can be anything 2012-05-10T10:07:39 data? 2012-05-10T10:07:52 i just want to store the strings 2012-05-10T10:07:55 My trie is used to re-trie-ve data 2012-05-10T10:08:08 i dont want that 2012-05-10T10:08:14 Trie!string trie; trie["abc"] = "the data"; 2012-05-10T10:08:15 hwo do i instantiate? 2012-05-10T10:08:26 Trie(bool) trie; 2012-05-10T10:08:29 ? 2012-05-10T10:08:37 yes, that's what you want: Trie!bool 2012-05-10T10:08:42 I use that often myself 2012-05-10T10:09:13 or Trie!(bool). The () are optional in such cases 2012-05-10T10:11:01 mleise: cannot implicitely convert char[] to string 2012-05-10T10:11:20 i need to make a string from 'line' 2012-05-10T10:11:39 i doesnt have the '\n' in it right? 2012-05-10T10:12:11 no, not by default 2012-05-10T10:12:19 and it *is* a string already 2012-05-10T10:12:48 mleise: marco.d(197): Error: function marco.Trie!(bool).Trie.opIndexAssign (bool item, string key) is not callable using argument types (bool,char[]) 2012-05-10T10:12:51 marco.d(197): Error: cannot implicitly convert expression (line) of type char[] to string 2012-05-10T10:14:48 so it is not immutable, maybe a direct view of the file buffer :D. Use "line.idup" to make an immutable copy 2012-05-10T10:15:09 a string is actually an alias for immutable(char)[] 2012-05-10T10:17:12 well its slow 2012-05-10T10:17:29 maybe im messing up something 2012-05-10T10:17:35 the haskell one runs in 2.1 secs 2012-05-10T10:17:51 ^C 2012-05-10T10:20:24 I don't know what you are doing, but as I said, it was made for lookup of tokens in a parser. If you mostly add long strings it will suck. Lookup should be amazingly fast though 2012-05-10T10:20:48 it is still loading the file 2012-05-10T10:20:55 Oo 2012-05-10T10:21:16 lol, you will run out of memory 2012-05-10T10:21:24 better keep an eye on that 2012-05-10T10:21:25 why? 2012-05-10T10:21:39 53% 2012-05-10T10:21:42 lol 2012-05-10T10:21:44 if it is still loading it must be a huge file 2012-05-10T10:21:45 thats 3gb 2012-05-10T10:21:52 2.4MegaBytes 2012-05-10T10:22:05 so I just turned 2.4 MB into 3 GB?? 2012-05-10T10:22:09 yeah 2012-05-10T10:22:11 jesus 2012-05-10T10:22:19 time ./marco 2012-05-10T10:22:22 loading file 2012-05-10T10:22:24 done loading 2012-05-10T10:22:26 real 2m28.278s 2012-05-10T10:22:28 user 2m20.034s 2012-05-10T10:22:30 sys 0m7.886s 2012-05-10T10:22:44 lol 2012-05-10T10:23:11 time ./test words +RTS -K30M 2012-05-10T10:23:11 don't leave me hangin' there. do some lookup tests :) 2012-05-10T10:23:14 Starting... 2012-05-10T10:23:16 Computation time: 2.150 sec 2012-05-10T10:23:18 Done. 2012-05-10T10:23:20 real 0m4.245s 2012-05-10T10:23:22 user 0m3.793s 2012-05-10T10:23:24 sys 0m0.420s 2012-05-10T10:23:27 this is the haskell one, 2.15 is the checking phase 2012-05-10T10:24:07 i have to admit mine doest use 256 characters 2012-05-10T10:24:11 btw, which compiler options did you use? 2012-05-10T10:24:13 only from ! to ~ 2012-05-10T10:24:20 dmd -O marco.d 2012-05-10T10:24:46 ok, if GDC is not at hand use at least "dmd -O -release -inline" 2012-05-10T10:25:29 and you could theoretically cut the static array @ '~' 2012-05-10T10:25:51 mleise: i doubled approximately the charset, now it is form 0 to 255, minimal impact 2012-05-10T10:26:38 mleise: great, it allocates way faster this way 2012-05-10T10:26:50 but the impact on my implementation is probably bigger :) Try Trie[127] nodes; 2012-05-10T10:26:59 no 2012-05-10T10:27:06 ok 2012-05-10T10:27:06 this benchmark is convincing 2012-05-10T10:28:00 It says: Don't allocate like a maniac in D 2012-05-10T10:28:11 mleise: if you give me cpu time function and tell me how to check membership, ill try a re-read benchmark too 2012-05-10T10:28:49 (benchmark is no good, i dont want to make functions and pass arguments to measure) 2012-05-10T10:28:54 CPU time function? Use Posix stuff. Checking membership? what's that? 2012-05-10T10:29:16 trie["somestring"] == !null 2012-05-10T10:29:35 im not sure what the compiler will say 2012-05-10T10:29:52 why not if(trie["something"]) ? 2012-05-10T10:30:02 thats good 2012-05-10T10:30:11 after all you put bools into it 2012-05-10T10:30:16 i wasnt sure what happends if the stringis not in the trie 2012-05-10T10:30:21 gives false? 2012-05-10T10:30:23 (why would it?) 2012-05-10T10:30:32 yes, it returns the default for that data type 2012-05-10T10:30:37 bleh 2012-05-10T10:30:40 ok 2012-05-10T10:30:56 import Posix.clock()? 2012-05-10T10:30:56 i was cheating a little ;) no "maybe" 2012-05-10T10:32:13 i feel like being caged 2012-05-10T10:32:24 wheres the documentation? 2012-05-10T10:33:42 I don't know which posix function it was, but I declared one myself when I needed the memory footprint 2012-05-10T10:33:45 getrusage 2012-05-10T10:34:23 ah and now comes the other problem 2012-05-10T10:34:29 in my haskell code, the words are in a list 2012-05-10T10:34:36 but here i just read it into the trie 2012-05-10T10:34:46 so i cant check for them 2012-05-10T10:35:01 http://codepad.org/w4ROIeXG 2012-05-10T10:35:24 what do you want to check? 2012-05-10T10:35:40 mleise: http://sprunge.us/NMfX 2012-05-10T10:35:48 can you pls extend this? 2012-05-10T10:35:54 i suck at D obviously 2012-05-10T10:36:00 read the file into an array 2012-05-10T10:36:16 and add a loop for cheking whether it is in the trie 2012-05-10T10:36:34 and 2 time interval measurements 2012-05-10T10:36:43 wut? 2012-05-10T10:36:43 1 for the reading, 1 for the checking 2012-05-10T10:36:47 ok 2012-05-10T10:36:59 why the extra array? 2012-05-10T10:37:27 and when would i add the array items into the trie? 2012-05-10T10:38:22 read the lines into an array 2012-05-10T10:38:31 so that you can check them after you added them all 2012-05-10T10:38:41 you dont want to re-read them from the file 2012-05-10T10:38:48 or use a list 2012-05-10T10:38:52 thats good too 2012-05-10T10:39:30 you add them to the array when you read them and add them to the trie 2012-05-10T10:40:23 ok, and then I loop over all the items in the list and try to find them in the try. sounds simple 2012-05-10T10:40:47 yeah 2012-05-10T10:43:00 *** Areks has quit IRC (Ping timeout: 272 seconds) 2012-05-10T10:46:14 mleise: http://minus.com/mdEhkijBO/ this is the file with the words, if you want to try it yourslef 2012-05-10T10:46:25 cool thanks 2012-05-10T10:50:43 mcstar: I have some ... memory issues, haha 2012-05-10T10:52:26 yeah 2012-05-10T10:52:35 i dont remember what exactly 2012-05-10T10:54:25 how about some words that are not in the trie? 2012-05-10T10:54:54 what about them? 2012-05-10T10:55:56 mleise: you have to admit its nice how the haskell one fits into 30 lines 2012-05-10T10:58:04 yes it is nice :) 2012-05-10T10:58:21 mleise: if you want to try it, put my first paste into PrefixTrie.hs, and http://sprunge.us/jRUN into test.hs 2012-05-10T11:00:22 does the words file have duplicate entries? 2012-05-10T11:00:32 i dont think so 2012-05-10T11:00:42 but i doesnt matter, does it? 2012-05-10T11:02:42 *** kurnevsky has joined #aichallenge 2012-05-10T11:09:55 I sent you a mail. The program adds only every second entry to the trie and the result makes me suspicious 2012-05-10T11:10:17 *** epicmonkey has quit IRC (Ping timeout: 245 seconds) 2012-05-10T11:10:43 there are more matches than there should be if every word was unique 2012-05-10T11:11:46 oh 2012-05-10T11:12:00 halfed the key space, but get more hits re-reading? 2012-05-10T11:12:20 I get more than half the line number in hits 2012-05-10T11:12:42 like 120000 of 200000 2012-05-10T11:13:38 121069 instead of 109576 2012-05-10T11:13:59 mleise: but the load time is significantly better! 2012-05-10T11:14:00 yes, that looks wrong to me 2012-05-10T11:14:14 14667 ms 2012-05-10T11:14:21 instead of the previous 2.5 minutes 2012-05-10T11:15:09 I have 9 seconds with the binary I sent you. i guess i set march=native again ^^ 2012-05-10T11:17:23 i didnt recompile 2012-05-10T11:17:31 mleise: how did you make it so fast? 2012-05-10T11:17:41 I left out half the words ?! 2012-05-10T11:17:58 150/2=75 -> 15? 2012-05-10T11:18:00 to get a mix of existing and non-existing entries for the lookip 2012-05-10T11:18:19 I don't know ... maybe the garbage collector struggles more when more ram is used 2012-05-10T11:18:30 you didnt change your trie? 2012-05-10T11:19:26 I just made it 127 entries long 2012-05-10T11:19:42 219153/2. equals 109577. according to my Mathematica, now WTF is going on!!!??? 2012-05-10T11:19:42 and look at this: 63% ulong gc.gcx.Gcx.fullcollect(void*) 2012-05-10T11:20:14 what does your PrefixTrie return? 2012-05-10T11:20:28 True 2012-05-10T11:20:29 the words are all unique according to sort -u | wc -l 2012-05-10T11:20:48 how about: I found x matches? 2012-05-10T11:20:51 ah sorry 2012-05-10T11:21:00 PrefixTrie doesnt return anythng 2012-05-10T11:21:03 its a data type 2012-05-10T11:21:22 but the test code returns the last result, which will be true 2012-05-10T11:21:27 and all are found btw 2012-05-10T11:21:35 but i can change it to all 2012-05-10T11:21:37 'all' 2012-05-10T11:21:53 add only every second word to the prefixtrie 2012-05-10T11:22:19 something is wrong with my implementation I bet 2012-05-10T11:23:22 mleise: change 'last $ map (contains dict) words' to 'all id $ map (contains dict) words' 2012-05-10T11:24:15 interesting 2012-05-10T11:24:26 17.802 2012-05-10T11:26:51 *** sigh has quit IRC (Remote host closed the connection) 2012-05-10T11:27:33 last doesnt force full evaluation it seems 2012-05-10T11:27:46 ill be afk for a bit 2012-05-10T11:31:32 *** cyphase has quit IRC (Ping timeout: 245 seconds) 2012-05-10T11:32:13 *** kilae has joined #aichallenge 2012-05-10T11:36:18 ok, it was nothing serious. Just some words like "red" are a prefix of "reddit" so if i look for "reddit" and it isn't in the trie, the longest match "red" is returned 2012-05-10T11:36:44 thus some non-existing entries got counted anyway. That's what I have the matchAllOrNothing method in the original code 2012-05-10T11:37:34 *** choas has joined #aichallenge 2012-05-10T11:39:41 *** thestinger has joined #aichallenge 2012-05-10T11:47:56 *** cyphase has joined #aichallenge 2012-05-10T11:49:20 cool, new github skin 2012-05-10T12:01:26 mleise: and that didnt cause problems for you? 2012-05-10T12:01:52 thestinger: 2012-05-10T12:01:56 ah he is here 2012-05-10T12:02:12 thestinger: do you have a prefix tree too? 2012-05-10T12:06:56 mcstar: no, I wanted the Trie to match "++" in "++i * 5];" 2012-05-10T12:07:01 http://www.file-upload.net/download-4348860/trie.zip.html 2012-05-10T12:07:17 mcstar: ^ try this. you wanted faster file load times. 2012-05-10T12:07:55 Or please wait 2012-05-10T12:07:58 00:14 2012-05-10T12:08:00 seconds 2012-05-10T12:08:02 wtf 2012-05-10T12:08:43 iLividSetupV1.exe? 2012-05-10T12:08:59 ?bad hoster? 2012-05-10T12:09:01 mleise: are you kidding with that link? 2012-05-10T12:09:12 sorry 2012-05-10T12:09:21 just send a mail 2012-05-10T12:09:24 my favorite one was shut down 2012-05-10T12:10:39 it's sent 2012-05-10T12:11:32 funny man 2012-05-10T12:12:17 what's so funny? 2012-05-10T12:12:25 ??? 2012-05-10T12:12:42 calloc for the win 2012-05-10T12:12:51 mleise: now this is way too fast 2012-05-10T12:12:55 XD 2012-05-10T12:13:03 thestinger: ?? 2012-05-10T12:13:10 hehe, poor Haskell 2012-05-10T12:13:39 well, poor or not, it made you change your code(which was broken) 2012-05-10T12:13:56 mleise: can it handle all words now? 2012-05-10T12:14:26 I used the matchallOrNothing routine in [] now, if that's what you mean 2012-05-10T12:14:32 i dont really understand why is the memory requirement is suddenly lower 2012-05-10T12:14:33 so it returns full matches only 2012-05-10T12:14:46 no i mean loading all the words form the file 2012-05-10T12:15:05 no it still only loads half of them 2012-05-10T12:15:18 calloc doesn't allocate physical memory until you write to it 2012-05-10T12:15:32 (on a 4KB memory page granularity) 2012-05-10T12:15:51 mleise: i know it loads half of them, it prints it 2012-05-10T12:15:59 im asking COULD it handle all of them 2012-05-10T12:16:01 and i guess yes 2012-05-10T12:16:39 oh ok :D 2012-05-10T12:16:46 mleise: why would calloc explain this? 2012-05-10T12:17:03 it must allocate a whole 256 element array when you write to one of its element 2012-05-10T12:17:16 or 127 or something 2012-05-10T12:17:23 the answer is yes, it uses 650 MB 2012-05-10T12:17:46 I optimized the array size to '~' - '!' + 1 ;) 2012-05-10T12:17:53 ill change back to 256 and load every word 2012-05-10T12:18:06 uh oh... 2012-05-10T12:19:12 *** kurnevsky has quit IRC (Ping timeout: 252 seconds) 2012-05-10T12:20:14 *** kurnevsky has joined #aichallenge 2012-05-10T12:20:16 mleise: ok, loa time 2.1, 2.2 seconds just like for haskell 2012-05-10T12:20:33 but 2012-05-10T12:20:38 what does it do in the end? 2012-05-10T12:21:26 time ./main words 2012-05-10T12:21:28 loading file 2012-05-10T12:21:30 loaded in 68 ms 2012-05-10T12:21:32 added 219153 words to the trie in 2115 ms 2012-05-10T12:21:34 looking up entries 2012-05-10T12:21:36 found 219153 matches in 82 ms 2012-05-10T12:21:38 real 0m4.762s 2012-05-10T12:21:40 user 0m3.083s 2012-05-10T12:21:42 sys 0m1.677s 2012-05-10T12:21:44 try adding it up 2012-05-10T12:22:11 try the gcc patricia trie 2012-05-10T12:22:15 maybe it takes 2 seconds to free up memory 2012-05-10T12:22:16 it frees 1,7 GB memory 2012-05-10T12:22:38 mleise: but it just should give it back 2012-05-10T12:22:39 just delete the destructor ~this() ;) 2012-05-10T12:22:43 why does it take that long? 2012-05-10T12:23:10 i believe it allocates very 'fragmentically' 2012-05-10T12:23:19 haha 2012-05-10T12:23:36 no the destructor calls add up 2012-05-10T12:24:33 mleise: the haskell version returns the moment it prints the result 2012-05-10T12:24:44 and i belive i cannot allocate less than your mutable version 2012-05-10T12:24:47 it* 2012-05-10T12:24:59 :( 2012-05-10T12:26:15 what's the lookup time for the haskell version compared to the D version? 2012-05-10T12:27:14 16seconds 2012-05-10T12:27:26 vs. your unbelievable 80ms 2012-05-10T12:28:10 but i have a guess why its so high 2012-05-10T12:29:15 that put a smile upon my face 2012-05-10T12:29:23 XD 2012-05-10T12:29:30 "You should measure fill up time" 2012-05-10T12:29:42 nah, why, when my lookups are so fast 2012-05-10T12:29:47 hahaha 2012-05-10T12:29:49 what are we benchmarking? :P 2012-05-10T12:29:52 thats just half of the sotry 2012-05-10T12:30:01 thestinger: two prefix trees 2012-05-10T12:31:10 what's the words file though? 2012-05-10T12:33:15 thestinger: http://minus.com/mdEhkijBO/ 2012-05-10T12:33:41 so what's the benchmark? 2012-05-10T12:33:47 put them all in a trie and then what? 2012-05-10T12:34:17 measure that you put it in 2012-05-10T12:34:22 measure that you check all of them 2012-05-10T12:34:23 thestinger: my version: https://www.dropbox.com/sh/f9ipis01tcpkou6/5nXglvdSGK/trie.zip 2012-05-10T12:34:44 oh, so add every 2nd word and then do a lookup for each? 2012-05-10T12:35:00 no 2012-05-10T12:35:02 add every one 2012-05-10T12:35:16 mleise just had memory problems before 2012-05-10T12:35:26 and he didnt remember to add every one of them 2012-05-10T12:36:28 mleise: i think you tweaked your code, to return true immediately, whatever the query is 2012-05-10T12:36:44 that would explain the speed 2012-05-10T12:37:03 ok, I'll upload a fixed version with 256 nodes and all words 2012-05-10T12:37:23 but I don't like the loading times that will result from it ;) 2012-05-10T12:37:30 so add every other word 2012-05-10T12:37:33 but do a lookup for each 2012-05-10T12:37:41 to verify that mcstar is wrong :P 2012-05-10T12:37:57 mleise: nono i measured that 2012-05-10T12:38:00 its ok 2012-05-10T12:38:12 mleise: problem is i cant read your code :( 2012-05-10T12:38:26 and i made that funny explanation to explain the speed 2012-05-10T12:39:35 there is some inlining going on, no question 2012-05-10T12:39:45 the [] method isn't actually 'called' 2012-05-10T12:40:15 mleise: can yo explain this? http://pastebin.com/zqqyBgMR 2012-05-10T12:41:21 mleise: how are you doing it without a marker on each node? to make the terminal ones 2012-05-10T12:41:40 thestinger: seen my code? 2012-05-10T12:41:51 oh, data? 2012-05-10T12:41:57 what does data hold? the whole value? 2012-05-10T12:42:34 i just dont see how his code walks the tree 2012-05-10T12:42:39 a marker on each node? 2012-05-10T12:42:42 i see an oracle 2012-05-10T12:42:52 ["cat", "catacomb"] 2012-05-10T12:42:54 hehe maybe it is, I like delphi 2012-05-10T12:43:04 c -> a -> [t] -> a -> c -> o -> m -> [b] 2012-05-10T12:43:34 I just exit when I find no pointer to the next node 2012-05-10T12:46:01 thestinger: this is the representation of ["cat", "catacomb"] http://pastebin.com/rDvX6DDQ 2012-05-10T12:46:24 (by deriving Show) 2012-05-10T12:46:26 nice innit? 2012-05-10T12:48:42 I certainly mixed payload and terminal node status 2012-05-10T12:49:03 is it a set or a map? 2012-05-10T12:49:41 for my map trie I used boost::optional (Maybe in haskell) 2012-05-10T12:49:45 for the set I just used a bool 2012-05-10T12:50:10 let me just delete the irrelevant stuff like the iterators and erase method 2012-05-10T12:50:18 corrected version: http://dl.dropbox.com/u/62255329/trie.zip 2012-05-10T12:50:35 have fun 2012-05-10T12:51:05 thestinger: what is a set or a map? 2012-05-10T12:51:43 the trie 2012-05-10T12:51:47 I don't understand what node.data is 2012-05-10T12:51:47 mleise: so you are storing the pointers to the read-in strings in the trie? 2012-05-10T12:52:00 what? no! 2012-05-10T12:52:18 I store pointers to the trie-nodes containing the next character to look up 2012-05-10T12:52:32 what's the data member for? 2012-05-10T12:52:42 data == payload 2012-05-10T12:53:01 then what is nodes? 2012-05-10T12:53:03 so it's a map of string->value? 2012-05-10T12:53:09 or it's just the string? 2012-05-10T12:53:12 If the string is "r" I start at the root node and see if the 'r'th entry exists (pointer to it is not null) 2012-05-10T12:53:31 the 'r'th entry in the nodes array 2012-05-10T12:53:44 It has 256 entries to cover every possible byte value 2012-05-10T12:54:35 f (node is null) return data; 2012-05-10T12:54:38 if (node is null) return data; 2012-05-10T12:54:38 so 'r' is -> nodes[114] 2012-05-10T12:54:40 why? 2012-05-10T12:55:30 hacking. remember I return the default value 0 if an entry isn't there? 2012-05-10T12:55:36 that's what happens here 2012-05-10T12:55:48 I assume the data at this point to be the default 2012-05-10T12:55:57 mleise: im losing imperative code-ground :( 2012-05-10T12:56:32 I could have written return false; 2012-05-10T12:56:53 hey, maybe that's faster 2012-05-10T12:57:49 yes it is !!! thanks 2012-05-10T12:58:14 I'll make it non-templated too so it doesn't need boost::array :P 2012-05-10T12:58:37 std::array doesn't work with incomplete types 2012-05-10T12:58:51 it actually did with gcc 4.6 but now it yells at you 2012-05-10T12:59:52 mcstar: That return data was actually needed when I returned something for "a" in "abcdef" 2012-05-10T13:00:07 but now that I match the whole string I can just return false there 2012-05-10T13:00:20 great 2012-05-10T13:00:30 why the hell is my lookup so slow 2012-05-10T13:00:43 mcstar: how are you storing the children? 2012-05-10T13:00:51 thestinger: in cages 2012-05-10T13:00:56 anyway I'll be back in a bit :P 2012-05-10T13:01:09 thestinger: http://hpaste.org/68330 2012-05-10T13:01:13 rwest: your children 2012-05-10T13:01:25 they want daddy 2012-05-10T13:01:52 If I have children, nobody has told me 2012-05-10T13:02:05 rwest: you were too drunk to remember 2012-05-10T13:02:08 XD 2012-05-10T13:02:26 even faster version (yay!): http://dl.dropbox.com/u/62255329/trie.zip 2012-05-10T13:02:50 mleise: my problem is, that it seem to add the items real fast(<4s), but takes 16seconds to check them? 2012-05-10T13:02:51 lol what's going on here 2012-05-10T13:03:08 mcstar: I speak no haskell 2012-05-10T13:03:35 With these high level languages it is always difficult to figure out what they do under the hood 2012-05-10T13:03:37 akkor probald meg ezt, most jobb? 2012-05-10T13:03:46 yes, that! 2012-05-10T13:04:07 mleise: i could go and profile... 2012-05-10T13:04:16 but instead im just gonna stare at it real mean 2012-05-10T13:05:00 hey, you still cheat with upper and lower bounds! 2012-05-10T13:05:10 thats the first paste 2012-05-10T13:05:43 (im not going to repaste for 2 character change) 2012-05-10T13:06:32 :p 2012-05-10T13:07:43 Well I guess, you can't really make it faster in ideomatic Haskell code 2012-05-10T13:07:57 not so sure 2012-05-10T13:08:00 Like I had to use calloc, to get the loading time improvement 2012-05-10T13:08:46 i could preallocate in a huge vector, and just use chunks from that 2012-05-10T13:08:51 -in 2012-05-10T13:09:10 or really use the State monad, and have steful updates 2012-05-10T13:09:14 or whatever 2012-05-10T13:09:18 there are options 2012-05-10T13:09:28 mleise: im very much a newbie to haskell 2012-05-10T13:12:35 sounds complicated :-/ 2012-05-10T13:23:22 what the ... 2012-05-10T13:23:26 this is surreal 2012-05-10T13:23:36 it must be... wrong 2012-05-10T13:24:19 what? 2012-05-10T13:25:10 no it was a bug 2012-05-10T13:30:09 you're all always here in the middle of the night :( 2012-05-10T13:31:25 depends on where you are 2012-05-10T13:31:32 time is relative 2012-05-10T13:36:30 *** thestinger has quit IRC (Quit: WeeChat 0.3.7) 2012-05-10T13:37:38 *** epicmonkey has joined #aichallenge 2012-05-10T13:43:01 mleise: im profiling, and it seems im allocating the whole time 2012-05-10T13:43:41 probably lookups are fast, but it is generating the trie just before that 2012-05-10T13:44:42 oh that's bad 2012-05-10T13:44:55 can you materialize the trie somehow? 2012-05-10T13:45:32 http://i.imgur.com/vaiKZ.png 2012-05-10T13:45:36 that wont help 2012-05-10T13:45:45 it would still be slower overall than yours 2012-05-10T13:45:54 but i can measure lookup a second time 2012-05-10T13:46:55 well, the lookup is 200 times slower than mine. there must be something you can do 2012-05-10T13:47:19 how did you measure that? 2012-05-10T13:47:27 i dont know how much time the lookup takes 2012-05-10T13:47:29 you said 16 seconds? 2012-05-10T13:47:37 correction now i do 2012-05-10T13:47:45 checking took 0.197 sec 2012-05-10T13:47:49 ah 2012-05-10T13:47:55 16 for the first time 2012-05-10T13:48:00 that's much much saner 2012-05-10T13:48:01 but it isnt pure lookup 2012-05-10T13:48:08 i think you get it 2012-05-10T13:50:59 mleise: this actually has a benefit, in a real application, it might happen that you dont look up every key, so this way you can save memory 2012-05-10T13:57:04 *** dvladim has joined #aichallenge 2012-05-10T14:15:12 *** Chris_0076 has quit IRC (Quit: Leaving) 2012-05-10T14:15:40 *** Chris_0076 has joined #aichallenge 2012-05-10T14:15:56 *** Chris_0076 has quit IRC (Remote host closed the connection) 2012-05-10T14:17:19 *** ramn has quit IRC (Ping timeout: 244 seconds) 2012-05-10T14:51:34 *** amstan has quit IRC (Quit: Konversation terminated!) 2012-05-10T14:54:16 *** amstan has joined #aichallenge 2012-05-10T14:54:18 *** amstan has joined #aichallenge 2012-05-10T14:54:18 *** ChanServ sets mode: +o amstan 2012-05-10T14:59:10 *** coeus has quit IRC (Ping timeout: 244 seconds) 2012-05-10T14:59:28 *** dvladim has quit IRC (Ping timeout: 248 seconds) 2012-05-10T15:12:26 *** janzert has left #aichallenge 2012-05-10T15:30:10 *** iglo has joined #aichallenge 2012-05-10T15:52:00 *** Accoun has quit IRC () 2012-05-10T16:07:04 *** Accoun has joined #aichallenge 2012-05-10T16:07:32 *** janzert has joined #aichallenge 2012-05-10T16:18:11 *** coeus has joined #aichallenge 2012-05-10T16:21:05 *** epicmonkey has quit IRC (Ping timeout: 256 seconds) 2012-05-10T16:25:37 *** kilae has quit IRC (Quit: ChatZilla 0.9.88.2 [Firefox 12.0/20120420145725]) 2012-05-10T16:25:52 mleise: i have a small consolation, the Data.Trie module takes 1 sec longer than mine 2012-05-10T16:26:17 :p 2012-05-10T16:33:57 *** thestinger has joined #aichallenge 2012-05-10T16:34:12 http://www.youtube.com/watch?feature=player_embedded&v=jD1lkIa2fno#! 2012-05-10T16:35:32 *** kurnevsky has quit IRC (Quit: Leaving.) 2012-05-10T16:40:23 "how do you resist grabbing the wheel?" 2012-05-10T16:40:36 "we've tested it a lot, and i kind of trust it" 2012-05-10T16:40:51 yeah... 2012-05-10T16:42:26 self driving cars would be great for all-night drinking and also extra sleep on the way to work 2012-05-10T16:43:55 rwest: and when you finally get to work, you turn on the automated software authoring system? 2012-05-10T16:44:01 XD 2012-05-10T16:44:10 No, I turn on reddit 2012-05-10T16:44:47 I really need to write an AI that writes software for me 2012-05-10T16:44:57 But then they wouldn't need me 2012-05-10T16:44:59 hmmmm 2012-05-10T16:45:22 unless!! 2012-05-10T16:45:29 I obfuscate the AI's code 2012-05-10T16:45:31 then they need me 2012-05-10T16:45:37 ok done deal, new project 2012-05-10T16:47:49 let me know when you succeed 2012-05-10T16:47:57 see you in 15 years 2012-05-10T16:49:20 my opinion is that we wont be needing cars much longer 2012-05-10T16:49:38 well just jack in the VR and that would be all 2012-05-10T16:49:53 you can go whereever you want in no time 2012-05-10T16:49:56 and at minimal const 2012-05-10T16:49:59 cost* 2012-05-10T16:50:10 and we will be FAT 2012-05-10T16:50:15 (well, not me) 2012-05-10T16:50:15 Surrogates coming up! 2012-05-10T16:50:19 yeah 2012-05-10T16:50:24 that movie exactly 2012-05-10T16:50:30 fuck that 2012-05-10T16:50:45 it is a plausible future 2012-05-10T16:50:50 not really 2012-05-10T16:50:58 why not? 2012-05-10T16:51:03 Religion 2012-05-10T16:51:08 (ok, maybe not surrogates, but this VR thing) 2012-05-10T16:51:14 religion who? 2012-05-10T16:51:35 what do you mean by religion? is it a rock band? 2012-05-10T16:51:42 You know, that thing, that 95% of the population believes in 2012-05-10T16:51:58 95? that high? 2012-05-10T16:52:01 yea 2012-05-10T16:52:01 noway 2012-05-10T16:52:05 pretty sad huh? 2012-05-10T16:52:15 i dont think theyre true believers 2012-05-10T16:52:56 anyway, gotta catch the train 2012-05-10T16:52:59 later 2012-05-10T16:53:40 you see? you are travelling unncessarily 2012-05-10T16:53:51 have a safe trip 2012-05-10T16:59:01 *** Garf has quit IRC (Read error: Connection reset by peer) 2012-05-10T17:00:04 *** delt0r has quit IRC (Ping timeout: 244 seconds) 2012-05-10T17:02:23 *** foRei has quit IRC (Read error: Connection reset by peer) 2012-05-10T17:03:28 *** foRei has joined #aichallenge 2012-05-10T17:04:18 *** Garf has joined #aichallenge 2012-05-10T17:05:32 *** amstan has quit IRC (Quit: Konversation terminated!) 2012-05-10T17:09:02 *** amstan has joined #aichallenge 2012-05-10T17:09:20 *** ChanServ sets mode: +o amstan 2012-05-10T17:13:52 *** delt0r has joined #aichallenge 2012-05-10T17:16:35 *** mcstar has quit IRC (Quit: mcstar) 2012-05-10T17:21:26 *** antimatroid1 has joined #aichallenge 2012-05-10T17:21:26 *** antimatroid has quit IRC (Read error: Connection reset by peer) 2012-05-10T17:23:59 *** choas has quit IRC (Read error: Operation timed out) 2012-05-10T17:26:41 *** Palmik has quit IRC () 2012-05-10T17:41:12 *** Kingpin13 has joined #aichallenge 2012-05-10T17:52:53 *** heinrich5991 has quit IRC (Ping timeout: 252 seconds) 2012-05-10T17:58:32 *** heinrich5991 has joined #aichallenge 2012-05-10T18:04:25 *** Fandekasp has joined #aichallenge 2012-05-10T18:09:48 *** ecidforiap has joined #aichallenge 2012-05-10T18:10:15 *** janzert1 has joined #aichallenge 2012-05-10T18:10:24 *** archdori has joined #aichallenge 2012-05-10T18:13:10 *** janzert has quit IRC (Read error: Connection reset by peer) 2012-05-10T18:14:01 *** pairofdice has quit IRC (Ping timeout: 260 seconds) 2012-05-10T18:14:01 *** ecidforiap is now known as pairofdice 2012-05-10T18:14:08 *** Fandekasp has quit IRC (Ping timeout: 248 seconds) 2012-05-10T18:22:19 *** iglo has quit IRC (Remote host closed the connection) 2012-05-10T18:27:54 *** amstan has quit IRC (Quit: Konversation terminated!) 2012-05-10T18:28:09 *** amstan has joined #aichallenge 2012-05-10T18:28:09 *** ChanServ sets mode: +o amstan 2012-05-10T18:42:33 *** amstan has quit IRC (Quit: Konversation terminated!) 2012-05-10T18:52:36 *** mleise has quit IRC (Quit: Leaving.) 2012-05-10T19:12:46 *** mceier has quit IRC (Quit: leaving) 2012-05-10T19:14:37 *** Kingpin13 has quit IRC (Ping timeout: 240 seconds) 2012-05-10T19:57:07 *** Garf has quit IRC (Quit: Make a new plan, Stan!) 2012-05-10T20:08:45 *** thestinger has quit IRC (Quit: WeeChat 0.3.7) 2012-05-10T20:32:26 *** That_Snail has joined #aichallenge 2012-05-10T20:44:07 *** replore has joined #aichallenge 2012-05-10T21:10:37 *** Fandekasp has joined #aichallenge 2012-05-10T21:14:07 *** archdori has quit IRC (Ping timeout: 240 seconds) 2012-05-10T21:33:01 *** That_Snail has left #aichallenge 2012-05-10T21:46:48 *** scribble has joined #aichallenge 2012-05-10T21:49:22 *** amstan has joined #aichallenge 2012-05-10T21:49:22 *** ChanServ sets mode: +o amstan 2012-05-10T21:56:29 *** alehorst has joined #aichallenge 2012-05-10T22:04:20 *** Chris_0076 has joined #aichallenge 2012-05-10T22:06:49 *** alehorst has quit IRC (Read error: Connection reset by peer) 2012-05-10T22:10:27 *** pairofdice has quit IRC (Quit: in girum imus nocte et consumimur igni) 2012-05-10T23:15:35 *** amstan has quit IRC (Quit: Konversation terminated!) 2012-05-10T23:21:38 *** dvladim has joined #aichallenge 2012-05-10T23:27:12 *** dvladim has quit IRC (Ping timeout: 248 seconds) 2012-05-10T23:29:18 *** amstan has joined #aichallenge 2012-05-10T23:29:22 *** amstan has quit IRC (Changing host) 2012-05-10T23:29:22 *** amstan has joined #aichallenge 2012-05-10T23:29:22 *** ChanServ sets mode: +o amstan 2012-05-10T23:44:24 *** scribble has quit IRC ()