2012-09-15 00:00 <wpwrak> quicksort moves a lot of things around. i don't need this. i can have this information in the code flow.
2012-09-15 00:02 <mth> what I described matches the "Partition-based general selection algorithm" section on that page
2012-09-15 00:03 <wpwrak> yeah. i basically want to unroll the thing.
2012-09-15 00:04 <wpwrak> like in the thee variables example. that one was small enough to keep in my head. i'm less optimistic about five ;-)
2012-09-15 00:04 <mth> the median of medians approach sounds useful
2012-09-15 00:04 <mth> you could do that with groups of 3 as well, if your poor little CPU doesn't have many regs
2012-09-15 00:05 <mth> you'd probably need special cases for sizes that are not powers of 3
2012-09-15 00:05 <mth> treating non-existing elements as infinity should be sufficient, I think
2012-09-15 00:06 <mth> ah no, then you might not get the actual median
2012-09-15 00:06 <mth> the groups of 5 approach should work equally well for groups of 3
2012-09-15 00:06 <mth> you just have to do more passes then
2012-09-15 00:07 <wpwrak> hmm. maybe i should draw the thing. maybe 5 is still manageable with a clear head.
2012-09-15 00:09 <wpwrak> since all this shold be n log n ... let's see ... 3 -> 2*3 = 6. i have 5 comparisons, close enough :)
2012-09-15 00:09 <mth> 5! = 120, so you can do an exhaustive test on the median-of-5-elements code
2012-09-15 00:10 <wpwrak> naw, it can't be worse than n log n
2012-09-15 00:10 <wpwrak> otherwise, i could just use quick- or heapsort
2012-09-15 00:10 <mth> I mean, you can just test all possible inputs and if your code passes it's ok
2012-09-15 00:11 <wpwrak> sure. but that's excessive. even bubble sort would do better ;-)
2012-09-15 00:11 <mth> well, maybe duplicate elements could be tricky, so you might need a bit more test cases, but still 5^5 is manageable
2012-09-15 00:12 <mth> just for testing, not when actually running
2012-09-15 00:12 <wpwrak> 5 log 5 is 11.6. so 12 is the goal :)
2012-09-15 00:12 <mth> eh, no-one said the constant was 1 ;)
2012-09-15 00:12 <wpwrak> ah yes, for testing the algorithm, i'll just do something like n^n. that runs on the pc, so cycles are dirt cheap :)
2012-09-15 00:13 <wpwrak> it's all a question of picking the right unit of measure ;)
2012-09-15 00:14 <mth> 12 decacompares :)
2012-09-15 00:15 <wpwrak> well, 16 bit comparisons are already bad enough on an 8 bit mcu :)
2012-09-15 00:18 <mth> hmm, could you do something per bit?
2012-09-15 00:19 <mth> if you look just at the most significant bit and count the number of 0s and the number of 1s, the median will belong to the largest of those two groups
2012-09-15 00:19 <wpwrak> sloooaawwwwly :) but probably per byte
2012-09-15 00:20 <wpwrak> actually, gcc may do that for me if it's smart about its data flow analysis and applies it to machine instructions and not the abstract 16 bit operations. not sure if it's that good, though.
2012-09-15 00:21 <mth> I mean a different algorithm, where you'd look at one bit at a time
2012-09-15 00:21 <wpwrak> hmm. that sounds O(n^2)-ish
2012-09-15 00:22 <mth> O(N * log R), where N is array length and R is range
2012-09-15 00:22 <wpwrak> but yes, interesting approach if word operations are wordsize-times as expensive as bit operations
2012-09-15 00:23 <wpwrak> actually a bit faster
2012-09-15 00:24 <wpwrak> you have N for the first bit. something in [N/2, N] for the second, etc.
2012-09-15 00:25 <wpwrak> well, depends on how quickly you can filter our the ones you already know don't fit
2012-09-15 00:25 <wpwrak> should be fun to implement in an FPGA :)
2012-09-15 00:26 <mth> is it allowed to shuffle elements around or should they stay at their starting indices?
2012-09-15 00:27 <wpwrak> i think a copy is about as expensive as a compare. a swap twice that.
2012-09-15 00:27 <wpwrak> or maybe 1.5 times
2012-09-15 00:27 <wpwrak> so copying is expensive
2012-09-15 00:28 <mth> swap is the ideal operation for this kind of thing anyway
2012-09-15 00:28 <wpwrak> but code is relatively cheap -> unrolling
2012-09-15 00:28 <wpwrak> naw, i need to select, not to reorder
2012-09-15 00:28 <wpwrak> of course, i could conceptually swap, without actually doing it
2012-09-15 00:28 <mth> ah
2012-09-15 00:29 <wpwrak> e.g., if you say if (a < b) { swap(a, b); return something_else(a, b); }
2012-09-15 00:29 <wpwrak> then one cuold simply if (a < b) return something_else(b, a);
2012-09-15 00:29 <wpwrak> that's basically how you could read my 3 values example
2012-09-15 00:30 <wpwrak> there is no copying/swapping there
2012-09-15 00:30 <mth> ok, you swap variables, not array elements
2012-09-15 00:41 <mth> is it OK if the algorithm only works for odd-length arrays?
2012-09-15 00:44 <wpwrak> that's fine, yes
2012-09-15 00:45 <wpwrak> avoids the pesky decision whether to pick v[(n-1)/2] or v[(n+1)/2] :)
2012-09-15 00:50 GCW2012 has left #qi-hardware [#qi-hardware]
2012-09-15 00:54 <mth> wpwrak: http://www.treewalker.org/temp/median-bitwise.py
2012-09-15 00:57 <mth> it figures out the value of the median one bit at a time
2012-09-15 00:57 <wpwrak> heh, pretty cool, yes
2012-09-15 00:57 <wpwrak> if you have an architecture where this is efficient, it's a very neat algorithm
2012-09-15 01:02 <wpwrak> lower/higher don't seem to make sense, though (except for preventing you from running into the asser)
2012-09-15 01:03 <mth> they contain the number of elements below and above the range that matches the mask
2012-09-15 01:03 <wpwrak> ah, right. you need that.
2012-09-15 01:04 <mth> usually I would add more comments, but it's 3 am here and the natural language part of my brain is half asleep
2012-09-15 01:05 <wpwrak> otherwise, the choice would be the most popular bits but not the median
2012-09-15 01:05 <mth> somehow python is easier than English :)
2012-09-15 01:05 <wpwrak> oh, it's pretty much self-documenting :)
2012-09-15 01:05 <mth> yes, it has to pick the middle element of the entire array, not just of the examined subarray
2012-09-15 01:06 <wpwrak> but .. 10 bits, 5 variables, and a relatively expensive inner loop .. that's something like a factor 10 more expensive than what whould be possible with a compare and branch approach
2012-09-15 01:08 <mth> it's simple and not hugely inefficient, but it might not be the best solution for you
2012-09-15 01:09 <wpwrak> yeah, i'm afraid it'll be a pencil and paper exercise. first the tree, then balancing it ...
2012-09-15 01:54 guanucoluis1 has quit [Remote host closed the connection]
2012-09-15 02:01 nikescar has quit [Read error: Connection reset by peer]
2012-09-15 02:02 nikescar has joined #qi-hardware
2012-09-15 02:03 rejon has joined #qi-hardware
2012-09-15 03:13 emeb has left #qi-hardware [#qi-hardware]
2012-09-15 03:36 DocScrutinizer05 has quit [Disconnected by services]
2012-09-15 03:36 DocScrutinizer05 has joined #qi-hardware
2012-09-15 03:37 Ayla has quit [Quit: dodo]
2012-09-15 04:09 ChanServ has quit [*.net *.split]
2012-09-15 04:12 cladamw has joined #qi-hardware
2012-09-15 04:15 emeb has joined #qi-hardware
2012-09-15 04:50 emeb has left #qi-hardware [#qi-hardware]
2012-09-15 05:43 rejon has quit [Ping timeout: 268 seconds]
2012-09-15 05:46 jekhor has joined #qi-hardware
2012-09-15 06:07 porchaso0 has joined #qi-hardware
2012-09-15 06:08 porchao has quit [Read error: Connection reset by peer]
2012-09-15 06:27 rejon has joined #qi-hardware
2012-09-15 06:32 cladamw has quit [Quit: Ex-Chat]
2012-09-15 06:36 rejon has quit [Ping timeout: 260 seconds]
2012-09-15 06:38 rejon has joined #qi-hardware
2012-09-15 06:47 scientes has quit [Ping timeout: 272 seconds]
2012-09-15 07:02 jekhor has quit [Ping timeout: 246 seconds]
2012-09-15 07:19 scientes has joined #qi-hardware
2012-09-15 08:02 scientes has quit [Remote host closed the connection]
2012-09-15 08:06 ChanServ has joined #qi-hardware
2012-09-15 08:16 kristoffer has joined #qi-hardware
2012-09-15 08:32 cladamw has joined #qi-hardware
2012-09-15 08:33 ChanServ has quit [shutting down]
2012-09-15 08:34 ChanServ has joined #qi-hardware
2012-09-15 08:49 porchao has joined #qi-hardware
2012-09-15 08:50 porchaso0 has quit [Read error: Connection reset by peer]
2012-09-15 09:04 aisa has quit [Ping timeout: 272 seconds]
2012-09-15 09:28 GNUtoo has joined #qi-hardware
2012-09-15 10:41 jluis has quit [Quit: Me'n vaig]
2012-09-15 10:41 jluis has joined #qi-hardware
2012-09-15 11:24 kuribas has joined #qi-hardware
2012-09-15 11:49 zear_ has joined #qi-hardware
2012-09-15 11:51 zear has quit [Ping timeout: 260 seconds]
2012-09-15 12:09 wej has quit [Ping timeout: 272 seconds]
2012-09-15 12:11 wej has joined #qi-hardware
2012-09-15 12:22 jurting_ has joined #qi-hardware
2012-09-15 12:26 Jurting has quit [Ping timeout: 268 seconds]
2012-09-15 12:33 cladamw has quit [Quit: Ex-Chat]
2012-09-15 12:45 rejon has quit [Ping timeout: 255 seconds]
2012-09-15 13:36 Hoolxi has joined #qi-hardware
2012-09-15 13:57 kuribas has quit [Quit: ERC Version 5.3 (IRC client for Emacs)]
2012-09-15 14:00 viric has quit [Quit: ep pleguem]
2012-09-15 14:02 rz2k has quit [Read error: Connection reset by peer]
2012-09-15 14:11 rz2k has joined #qi-hardware
2012-09-15 14:19 porchaso0 has joined #qi-hardware
2012-09-15 14:19 porchao has quit [Ping timeout: 244 seconds]
2012-09-15 14:32 Ayla has joined #qi-hardware
2012-09-15 14:34 <Ayla> larsc, hi
2012-09-15 14:35 <Ayla> I'd like to extend your ohci-jz4740 driver to other JZ devices
2012-09-15 14:35 <Ayla> mind if I just rename "jz4740" to just "jz" on the filename and the code?
2012-09-15 14:44 <larsc> Ayla: usually that's not done, just use the driver as is for the other devices
2012-09-15 14:44 xiangfu has joined #qi-hardware
2012-09-15 14:45 <Ayla> really.
2012-09-15 14:45 <Ayla> ?
2012-09-15 14:45 <Ayla> so I just copy-paste the code?
2012-09-15 14:45 <larsc> no
2012-09-15 14:46 <larsc> keep it as it is and extend it where necessary
2012-09-15 14:46 <larsc> but don't rename everything
2012-09-15 14:48 <Ayla> mmmhh
2012-09-15 15:02 Hoolxi has quit [Remote host closed the connection]
2012-09-15 15:18 <xiangfu> @tweet QEMU emulated Ben NanoNote http://youtu.be/q6BxbAtJ7F4
2012-09-15 15:19 <xiangfu> !tweet QEMU emulated Ben NanoNote http://youtu.be/q6BxbAtJ7F4
2012-09-15 15:19 <qi-bot>  Tweet created: http://twitter.com/qihardware
2012-09-15 15:21 <qi-bot> おさかな　たろう　 (RT Qi Hardware(1)): RT @qihardware: <xiangfu> QEMU emulated Ben NanoNote http://t.co/FYWEihuQ ( 246992014317604865@qihardware - 2s ago via TweetDeck )
2012-09-15 15:32 <whitequark> errr
2012-09-15 15:32 <whitequark> why qi-bot talks hiragana?!
2012-09-15 15:36 urandom__ has joined #qi-hardware
2012-09-15 15:36 aisa has joined #qi-hardware
2012-09-15 15:37 <larsc> why not?
2012-09-15 15:53 xiangfu has quit [Quit: Leaving]
2012-09-15 16:51 emeb has joined #qi-hardware
2012-09-15 17:20 <qi-bot> [commit] Mark Brown: ASoC: core: Try to use regmap if the driver doesn't set up any I/O (jz-3.5) http://qi-hw.com/p/qi-kernel/90ff125
2012-09-15 17:20 <qi-bot> [commit] Mark Brown: ASoC: core: Fix check before defaulting to regmap (jz-3.5) http://qi-hw.com/p/qi-kernel/82a40fe
2012-09-15 17:20 <qi-bot> [commit] Mark Brown: ASoC: io: Use dev_get_regmap() if driver doesn't provide a regmap (jz-3.5) http://qi-hw.com/p/qi-kernel/c21575f
2012-09-15 17:20 <qi-bot> [commit] Lars-Peter Clausen: ASoC: jz4740: Use regmap (jz-3.5) http://qi-hw.com/p/qi-kernel/d8b0b5c
2012-09-15 17:43 heberth has joined #qi-hardware
2012-09-15 17:50 viric_ has joined #qi-hardware
2012-09-15 18:00 zear_ is now known as zear
2012-09-15 18:01 viric_ is now known as viric
2012-09-15 18:08 heberth has quit [Ping timeout: 264 seconds]
2012-09-15 18:08 heberth has joined #qi-hardware
2012-09-15 18:10 LunaVorax has joined #qi-hardware
2012-09-15 18:11 heberth has quit [Client Quit]
2012-09-15 18:51 jurting_ is now known as jurting
2012-09-15 19:12 heberth has joined #qi-hardware
2012-09-15 19:15 jekhor has joined #qi-hardware
2012-09-15 20:18 Textmode has joined #qi-hardware
2012-09-15 20:18 dandon has quit [Read error: Connection reset by peer]
2012-09-15 20:32 dandon has joined #qi-hardware
2012-09-15 20:32 dandon has quit [Client Quit]
2012-09-15 20:36 dandon has joined #qi-hardware
2012-09-15 20:38 jekhor has quit [Ping timeout: 246 seconds]
2012-09-15 20:41 dandon_ has joined #qi-hardware
2012-09-15 20:42 dandon has quit [Ping timeout: 246 seconds]
2012-09-15 20:42 dandon_ is now known as dandon
2012-09-15 20:51 jurting has quit [Ping timeout: 252 seconds]
2012-09-15 20:52 jurting has joined #qi-hardware
2012-09-15 20:59 jow_laptop has quit [Remote host closed the connection]
2012-09-15 21:18 GCW2012 has joined #qi-hardware
2012-09-15 21:18 <GCW2012> anyone with knowledge about ITE IT6610 HDMI
2012-09-15 21:19 <GCW2012> or Vivante GC860 GPU
2012-09-15 21:33 woakas has quit [Ping timeout: 272 seconds]
2012-09-15 21:36 GNUtoo has quit [Quit: Program received signal SIGSEGV, Segmentation fault.]
2012-09-15 21:45 woakas has joined #qi-hardware
2012-09-15 22:03 GNUtoo has joined #qi-hardware
2012-09-15 22:06 kristoffer has quit [Quit: Leaving]
2012-09-15 22:11 GNUtoo has quit [Quit: Program received signal SIGSEGV, Segmentation fault.]
2012-09-15 22:30 GCW2012 has left #qi-hardware [#qi-hardware]
2012-09-15 22:30 heberth has quit [Quit: leaving]
2012-09-15 22:37 Textmode has quit [Ping timeout: 255 seconds]
2012-09-15 22:43 dandon_ has joined #qi-hardware
2012-09-15 22:45 dandon has quit [Ping timeout: 246 seconds]
2012-09-15 22:45 dandon_ is now known as dandon
2012-09-15 22:50 Textmode has joined #qi-hardware
2012-09-15 23:04 Textmode has quit [Ping timeout: 255 seconds]
2012-09-15 23:16 Textmode has joined #qi-hardware
2012-09-15 23:21 Textmode has quit [Max SendQ exceeded]