[00:00] MSG: Ping timeout: 245 seconds [00:04] Join: Metcalf joined #corewars [00:37] MSG: Ping timeout: 245 seconds [00:37] Join: Metcalf joined #corewars [01:00] MSG: Ping timeout: 245 seconds [01:02] Join: Metcalf joined #corewars [01:08] MSG: Ping timeout: 245 seconds [10:33] Join: Metcalf joined #corewars [10:36] Join: OoS joined #corewars [10:38] MSG: Ping timeout: 245 seconds [10:48] Join: yoR joined #corewars [10:48] Hi [10:49] Hi yoR :-) [10:49] I improved my Gnome sort ;-) [10:49] I've got a working quicksort.. [10:49] Yay! [10:49] How did you improve it? [10:50] outer mov }p, temp [10:50] p mov FIRST+LENGTH-1, {p [10:50] nop >y, }p [10:50] mov temp, }p [10:50] sne y, #LENGTH [10:50] nop inner slt *p, {p [10:50] y djn inner, #LENGTH-1 [10:50] jmn outer, y [10:51] your worst case = 4x^2 - 2x, mine = 4.5x^2 - 3.5x [10:53] I'm not sure how to analyse the worst case for Quicksort [10:53] Backwards is (I think) worstcase for mine [10:55] Quicksort is a bit big, but its in your mail [10:55] Thanks :-) [10:55] I take the first number as pivot point, and implemented the in-place version of quicksort [10:56] I'm not going to look yet, first I'm going to code mine [10:56] Hehe its a real pain in the.. [10:56] How long is yours? [10:57] 4 (dat) pointers, 24/25 lines of code [10:59] Randomly placed 1-20 integers take about 600 cycles, and placed from 20-1 takes about 1200 [11:03] Slower than insertion sort [11:03] But might be faster as the number gets bigger [11:03] Insertion sort = worst case 461 for 20 numbers [11:04] The worst case of quicksort is always very bad, but its now common [11:04] now>not [11:05] Most quicksorts use random pivot points.. I always use the first... so the worst case is obvious [11:10] I'm not sure if first or random is best [11:12] Well, random is hard to predict :) [11:15] MSG: Ping timeout: 245 seconds [11:15] Join: OoS joined #corewars [11:16] I was going to try an average pivot [11:17] Takes more time to look up the average.. [11:17] Join: fiveop joined #corewars [11:17] Hi Fiveop [11:17] hi [11:24] hi folks [11:24] hiya miz [11:25] Hi Mizcu [11:33] so where's your tiny contribution Roy? :P [11:35] Most of Roy's tiny warriors are published already :-) [11:35] * OoS ought to make the next issue of tiny warrior [11:49] What OoS says, I think I published most, all that are pushed off anyway [11:50] MSG: Ping timeout: 245 seconds [11:50] And Sneaky Spike 2, my only alive tiny warrior...isnt very special, pretty boring oneshot actually [11:50] Join: OoS joined #corewars [11:52] smallness is quite sofisticated, qbomb -> most simple sd-clear :P [11:53] sophisticated it is :/ [11:53] Heh, they don't have to be.. [11:55] obviously not no ;) [11:55] All 4 of my tiny hill warriors are published [11:55] Moomintroll / Digital Swarm have a tiny qscan which was interesting to write [11:58] JM: Just mailed you the improved quicksort [11:58] No peeking yet ;-) [11:59] then why did you send it, if there is to be no peeking? [12:00] So I can look when I'm ready. :-) Can I have some stats please Roy? Size, speed :-P [12:01] still your clib in redcode thing? :) [12:02] Mizcu: He told me he doesn't want to see it (yet) but wants it in his mail, so I warn him [12:03] Worstcase: 1430+ (probably) just found that out [12:03] Its silly, 1 to 20 is slower :) [12:08] Yes, I think Knuth say's something like that [12:10] fiveop: I agreed to write some stuff about real programming in redcode, so I'm writing an article comparing different sort techniques. [12:11] agreed to whom? [12:11] and that's why there are these things called randomised algorithms ;) [12:14] MSG: Ping timeout: 245 seconds [12:19] Join: Metcalf joined #corewars [12:19] randomized algorithms? [12:20] Like Bogosort you mean? O(nn!) on average, worst case O(infinity) :-) [12:24] "For those inputs, observers would be surprised by mysterious failures of the computer or improbable accidents preventing its operation because all universes in which it did operate are destroyed." [12:24] - bogosort on wikiwikipedia [12:26] JM: Improved the algorithm some, now worstcase is 1250ish [12:33] JM: If you really want to impress with the sorting, try making it parallel [12:33] Join: OoS joined #corewars [12:36] MSG: Ping timeout: 245 seconds [12:37] Maybe for mergesort [12:38] Could also be done for quicksort, but all the processes must use different pointers, which requires copying code, which is slow.. [12:45] OoS, the insertionsort you mailed is pretty fast in redcode, when placed against my quicksort is wins with sequences 1-N and N-1... but with random numbers quicksort wins [12:45] Join: Metcalf joined #corewars [12:46] MSG: Ping timeout: 245 seconds [12:46] So the worst case is better, but the average worse [12:46] Much... yes [12:46] I haven't got a clue how to calculate the average time for quicksort [12:47] But there is still a error in my code I think, I don't understand why 1-20 and 20-1 are both the worsed I found yet [12:47] Quicksort? How are you choosing your pivot? [12:48] Picking the first element [12:48] Well known failure case for quicksort as you don't get any "divide and conquer" that way. [12:49] Thats true.. but since we haven't got a random-function yet this was easiest ;) [12:49] Consider 1, 2, 3, 4, 5. Pivot on 1. You split your list into [], 1, [2, 3, 4, 5]. You then repeat on the [2, 3, 4, 5] list and have the same problem. [12:50] Reversed its almost the same.. [5] [1,2,3,4] [12:50] One thing to do is to pick your pivot as the element half-way through the unsorted list. Doesn't make any difference for randomly sorted lists, but means it works perfectly for already sorted lists. [12:50] err, [5],[4,3,2,1] [12:50] But costs extra lines to implement.. damn :) [12:51] Pays your money, makes your choice :-) [12:51] MSG: Ping timeout: 245 seconds [12:52] Join: Metcalf joined #corewars [12:53] Hi Phil [12:53] True, I'll swallow [12:53] I really hate seeing the instruction add #1, somewhere :-( [12:53] * yoR agrees [12:53] Even worse: sub #1 [12:54] even worse: jmp 2 [12:55] * yoR has that in his code... grrr [12:56] * Metcalf has it in his code too [12:56] This is also frustrating: slt/jmp/slt/jmp/sne/jmp [13:00] MSG: Ping timeout: 245 seconds [13:01] Join: Metcalf joined #corewars [13:28] MSG: Ping timeout: 245 seconds [13:28] Join: Metcalf joined #corewars [13:45] JM: Added about 10 lines now, the latest does 785 to sort 1-20 and 654 to sort 20-1 [13:45] Much better :-) [13:46] Well, looks better of course, but doesn't really change the worstcase [13:46] It just changes the worstcase... [13:46] :-( [13:46] Changing the pivot-point will never get you a better worstcase I think [13:47] In a real-world situation, it makes the worstcase less likely to occur as sort algorithms are "often" fed with already sorted data. [13:48] True, but this is CW, far from real world ;-) [13:48] So, we're back to "it depends what you care about" :-) [13:48] * yoR doesn't care a thing about sorting in CW, just likes to prorgam stuff [13:51] What is the smallest sorter you've got now JM? [13:53] Gnome, 9 lines. So longer than yours, but doesn't use sentinels [13:55] Selection, length 10, Insertion length 11, bubble ranges from 10 to 13. [13:55] Metcalf: randomized as in, first shuffle then sort for example, because some algorithms perfrom bad on nearly sorted input [13:56] Now we need to find a good shuffling algorithm! [13:57] you need a rng first ;) [14:02] MSG: Ping timeout: 245 seconds [14:02] Join: Metcalf joined #corewars [14:06] Join: OoS joined #corewars [14:06] MSG: Ping timeout: 245 seconds [14:10] Metcalf: In the mail, a gnomesort that is 7 lines [14:11] And its also a bit faster of course (one less line) [14:12] :-) [14:13] I could probably reverse it and make it even smaller :) [14:13] I'll try! [14:17] never hord of gnome sort [14:17] heard [14:19] There's some code in today's log fiveop [14:20] It's behaves similar to Insertion sort, but exchanges instead of moving [14:23] Your new Gnomesort is slower Roy [14:25] Worst case = 4.5x^2-1.5x-3 [14:27] Err.. if you say so :P [14:29] 1767 to sort 20...1 compared to 1560 for your previous version [14:29] I hate it when our fire alarm is tested ... [14:32] Not now I hope [14:32] It's raining here [14:57] MSG: Ping timeout: 245 seconds [14:57] Join: OoS joined #corewars [15:08] MSG: Ping timeout: 245 seconds [15:09] Join: OoS joined #corewars [15:10] I've put a few O(n^2) sort routines in http://corewar.co.uk/temp [15:10] I'm struggling to make a decent bubble sort [15:41] I made one..! [15:41] :-) [15:41] ptr dat table+LENGTH-1 , table+LENGTH-1 [15:41] switch dat 0 , 1 [15:41] mov.ab #2 , -1 [15:41] mov.ba @ptr , >ptr [15:41] mov.b @ptr , mov.ab >ptr , @ptr [15:41] start slt.b @ptr , jmn -1 , @ptr [15:41] jmn @switch , @ptr [15:41] reset mov.ab ptr , ptr [15:41] djn.b start , switch [15:41] dat 0 , 0 [15:41] LENGTH equ 20 [15:41] table dat 0 , 20 [15:41] n for 19 [15:41] dat 0,20-n [15:41] rof [15:41] end start [15:42] Small(ish) and not so fast (1830 worst) [15:43] Ilmari's bubble sort is 9 lines + 1 dat, 1406 worst [15:43] Sigh :) [15:43] Mine is 13 lines, 2001 worst [15:44] I thought I'd use one pointer for a change, got a cool swapping idea doing that [15:44] However, my average should be much better [15:44] Much better? why is that? [15:45] Any data above the last pointer to be exchanged on the last pass is in it's final position and doesn't need to be compared on the next pass [15:45] My code keeps track of that [15:47] Ah ok, thats a good improvement yes [15:48] Now I'm going to make a multiprocess bubbly [15:48] * OoS doesn't think that will work [15:48] Don't be naive ;-) [15:48] bubble sort isn't a divide and conquer algorithm [15:49] Just wait a couple of days before I give up ;-) I've got a neat idea [15:49] I'll wait for you to prove me wrong then :-P [16:02] MSG: Ping timeout: 245 seconds [16:03] Join: OoS joined #corewars [16:08] Bah, I give up [16:10] :-( [16:33] yoR: I've been testing some code with worst case 470 for 20 items :-P [16:34] But I haven't been able to prove it always works yet [16:34] Heh, what kind of scan? [16:35] Shellsort [16:45] MSG: Ping timeout: 245 seconds [16:45] Join: OoS joined #corewars [16:46] MSG: [18:03] MSG: Ping timeout: 245 seconds [18:04] Join: OoS joined #corewars [18:21] My Shellsort turned into a Comb Sort [18:26] MSG: Ping timeout: 245 seconds [18:27] Join: OoS joined #corewars [18:37] MSG: Quit: humhum [18:51] Join: elkauka joined #corewars [18:52] hi@all [18:53] i r back too [18:53] i just happend to run into pygments (http://pygments.org/) which to my surprise comes with a lexer for redcode - is any one of you using it somewhere? [18:54] Hi El Kauka :-) [18:55] * OoS goes to look [18:55] hi Oos [18:58] Join: Metcalf joined #corewars [19:01] MSG: Ping timeout: 245 seconds [19:01] Join: fiveop joined #corewars [19:02] MSG: Ping timeout: 245 seconds [19:12] MSG: Quit: humhum [19:13] just tried it out, highlights for redcode ar rather limited (comments and numbers basicly) but in the end there isn't much one could highlight in redcode anyway ;) [19:36] Join: Metcalf joined #corewars [19:43] MSG: Ping timeout: 245 seconds [19:46] Join: Metcalf joined #corewars [19:53] MSG: Ping timeout: 245 seconds [19:57] Join: Metcalf joined #corewars [19:59] MSG: Quit: and over there we have the labyrinth guards. one always lies, one tells the truth, and one stabs people who ask t [20:09] MSG: Ping timeout: 245 seconds [20:27] Join: fiveop joined #corewars [21:28] MSG: Quit: humhum [22:55] Join: elkauka joined #corewars [23:01] Join: fiveop joined #corewars [23:36] MSG: Quit: humhum