| 00:00.04 | wpwrak | quicksort moves a lot of things around. i don't need this. i can have this information in the code flow. |
| 00:02.17 | mth | what I described matches the "Partition-based general selection algorithm" section on that page |
| 00:03.45 | wpwrak | yeah. i basically want to unroll the thing. |
| 00:04.38 | wpwrak | like in the thee variables example. that one was small enough to keep in my head. i'm less optimistic about five ;-) |
| 00:04.38 | mth | the median of medians approach sounds useful |
| 00:04.57 | mth | you could do that with groups of 3 as well, if your poor little CPU doesn't have many regs |
| 00:05.32 | mth | you'd probably need special cases for sizes that are not powers of 3 |
| 00:05.44 | mth | treating non-existing elements as infinity should be sufficient, I think |
| 00:06.09 | mth | ah no, then you might not get the actual median |
| 00:06.50 | mth | the groups of 5 approach should work equally well for groups of 3 |
| 00:06.58 | mth | you just have to do more passes then |
| 00:07.34 | wpwrak | hmm. maybe i should draw the thing. maybe 5 is still manageable with a clear head. |
| 00:09.05 | wpwrak | since all this shold be n log n ... let's see ... 3 -> 2*3 = 6. i have 5 comparisons, close enough :) |
| 00:09.44 | mth | 5! = 120, so you can do an exhaustive test on the median-of-5-elements code |
| 00:10.08 | wpwrak | naw, it can't be worse than n log n |
| 00:10.31 | wpwrak | otherwise, i could just use quick- or heapsort |
| 00:10.43 | mth | I mean, you can just test all possible inputs and if your code passes it's ok |
| 00:11.35 | wpwrak | sure. but that's excessive. even bubble sort would do better ;-) |
| 00:11.44 | mth | well, maybe duplicate elements could be tricky, so you might need a bit more test cases, but still 5^5 is manageable |
| 00:12.03 | mth | just for testing, not when actually running |
| 00:12.13 | wpwrak | 5 log 5 is 11.6. so 12 is the goal :) |
| 00:12.58 | mth | eh, no-one said the constant was 1 ;) |
| 00:12.58 | 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 :) |
| 00:13.41 | wpwrak | it's all a question of picking the right unit of measure ;) |
| 00:14.00 | mth | 12 decacompares :) |
| 00:15.48 | wpwrak | well, 16 bit comparisons are already bad enough on an 8 bit mcu :) |
| 00:18.46 | mth | hmm, could you do something per bit? |
| 00:19.37 | 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 |
| 00:19.45 | wpwrak | sloooaawwwwly :) but probably per byte |
| 00:20.37 | 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. |
| 00:21.18 | mth | I mean a different algorithm, where you'd look at one bit at a time |
| 00:21.19 | wpwrak | hmm. that sounds O(n^2)-ish |
| 00:22.14 | mth | O(N * log R), where N is array length and R is range |
| 00:22.18 | wpwrak | but yes, interesting approach if word operations are wordsize-times as expensive as bit operations |
| 00:23.44 | wpwrak | actually a bit faster |
| 00:24.21 | wpwrak | you have N for the first bit. something in [N/2, N] for the second, etc. |
| 00:25.00 | wpwrak | well, depends on how quickly you can filter our the ones you already know don't fit |
| 00:25.09 | wpwrak | should be fun to implement in an FPGA :) |
| 00:26.36 | mth | is it allowed to shuffle elements around or should they stay at their starting indices? |
| 00:27.10 | wpwrak | i think a copy is about as expensive as a compare. a swap twice that. |
| 00:27.26 | wpwrak | or maybe 1.5 times |
| 00:27.49 | wpwrak | so copying is expensive |
| 00:28.12 | mth | swap is the ideal operation for this kind of thing anyway |
| 00:28.12 | wpwrak | but code is relatively cheap -> unrolling |
| 00:28.30 | wpwrak | naw, i need to select, not to reorder |
| 00:28.48 | wpwrak | of course, i could conceptually swap, without actually doing it |
| 00:28.53 | mth | ah |
| 00:29.14 | wpwrak | e.g., if you say if (a < b) { swap(a, b); return something_else(a, b); } |
| 00:29.29 | wpwrak | then one cuold simply if (a < b) return something_else(b, a); |
| 00:29.59 | wpwrak | that's basically how you could read my 3 values example |
| 00:30.19 | wpwrak | there is no copying/swapping there |
| 00:30.48 | mth | ok, you swap variables, not array elements |
| 00:41.34 | mth | is it OK if the algorithm only works for odd-length arrays? |
| 00:44.31 | wpwrak | that's fine, yes |
| 00:45.16 | wpwrak | avoids the pesky decision whether to pick v[(n-1)/2] or v[(n+1)/2] :) |
| 00:50.55 | *** part/#qi-hardware GCW2012 (~gcwnow@cpe-76-92-189-100.kc.res.rr.com) |
| 00:54.04 | mth | wpwrak: http://www.treewalker.org/temp/median-bitwise.py |
| 00:57.06 | mth | it figures out the value of the median one bit at a time |
| 00:57.28 | wpwrak | heh, pretty cool, yes |
| 00:57.54 | wpwrak | if you have an architecture where this is efficient, it's a very neat algorithm |
| 01:02.03 | wpwrak | lower/higher don't seem to make sense, though (except for preventing you from running into the asser) |
| 01:03.06 | mth | they contain the number of elements below and above the range that matches the mask |
| 01:03.53 | wpwrak | ah, right. you need that. |
| 01:04.59 | mth | usually I would add more comments, but it's 3 am here and the natural language part of my brain is half asleep |
| 01:05.14 | wpwrak | otherwise, the choice would be the most popular bits but not the median |
| 01:05.15 | mth | somehow python is easier than English :) |
| 01:05.35 | wpwrak | oh, it's pretty much self-documenting :) |
| 01:05.50 | mth | yes, it has to pick the middle element of the entire array, not just of the examined subarray |
| 01:06.40 | 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 |
| 01:08.06 | mth | it's simple and not hugely inefficient, but it might not be the best solution for you |
| 01:09.38 | wpwrak | yeah, i'm afraid it'll be a pencil and paper exercise. first the tree, then balancing it ... |
| 02:02.09 | *** join/#qi-hardware nikescar (~nikescar@114.199.131.108) |
| 02:03.15 | *** join/#qi-hardware rejon (~rejon@jp.fabricatorz.com) |
| 03:13.12 | *** part/#qi-hardware emeb (~ericb@ip72-201-79-123.ph.ph.cox.net) |
| 03:36.48 | *** join/#qi-hardware DocScrutinizer05 (~HaleBopp@openmoko/engineers/joerg) |
| 04:12.06 | *** join/#qi-hardware cladamw (~adamwang@host-174.163-235-182.cable.dynamic.kbtelecom.net) |
| 04:15.09 | *** join/#qi-hardware emeb (~ericb@ip72-201-79-123.ph.ph.cox.net) |
| 04:50.21 | *** part/#qi-hardware emeb (~ericb@ip72-201-79-123.ph.ph.cox.net) |
| 05:46.49 | *** join/#qi-hardware jekhor (~jek@leased-line-46-53-195-83.telecom.by) |
| 06:07.09 | *** join/#qi-hardware porchaso0 (~hato@eatkyo323155.adsl.ppp.infoweb.ne.jp) |
| 06:27.44 | *** join/#qi-hardware rejon (~rejon@122.70.25.10) |
| 06:38.21 | *** join/#qi-hardware rejon (~rejon@jp.fabricatorz.com) |
| 07:19.26 | *** join/#qi-hardware scientes (~scientes@199-188-193-145.PUBLIC.monkeybrains.net) |
| 08:06.59 | *** join/#qi-hardware ChanServ (ChanServ@services.) |
| 08:06.59 | *** mode/#qi-hardware [+o ChanServ] by lindbohm.freenode.net |
| 08:16.25 | *** join/#qi-hardware kristoffer (~kristoffe@c-9ed8e555.010-30-6c6b7012.cust.bredbandsbolaget.se) |
| 08:32.41 | *** join/#qi-hardware cladamw (~adamwang@host-174.163-235-182.cable.dynamic.kbtelecom.net) |
| 08:34.03 | *** join/#qi-hardware ChanServ (ChanServ@services.) |
| 08:34.03 | *** mode/#qi-hardware [+o ChanServ] by lindbohm.freenode.net |
| 08:49.33 | *** join/#qi-hardware porchao (~hato@eatkyo323155.adsl.ppp.infoweb.ne.jp) |
| 09:28.29 | *** join/#qi-hardware GNUtoo (~gnutoo@arc33-1-78-248-49-133.fbx.proxad.net) |
| 10:41.51 | *** join/#qi-hardware jluis (~jluis@31.Red-83-38-89.dynamicIP.rima-tde.net) |
| 11:24.35 | *** join/#qi-hardware kuribas (~user@94-227-88-230.access.telenet.be) |
| 11:49.20 | *** join/#qi-hardware zear_ (~zear@2001:0:5ef5:79fd:2465:2666:2abe:b43b) |
| 12:11.47 | *** join/#qi-hardware wej (~j@nl3x.mullvad.net) |
| 12:22.56 | *** join/#qi-hardware jurting_ (~jurting@ip-128-219-241-92.dialup.ice.net) |
| 13:36.10 | *** join/#qi-hardware Hoolxi (~Openfree@117.143.101.184) |
| 14:11.08 | *** join/#qi-hardware rz2k (~rzk@93-80-167-173.broadband.corbina.ru) |
| 14:19.09 | *** join/#qi-hardware porchaso0 (~hato@eatkyo570124.adsl.ppp.infoweb.ne.jp) |
| 14:32.05 | *** join/#qi-hardware Ayla (~paul@pc-144-230-164-190.cm.vtr.net) |
| 14:34.34 | Ayla | larsc, hi |
| 14:35.07 | Ayla | I'd like to extend your ohci-jz4740 driver to other JZ devices |
| 14:35.52 | Ayla | mind if I just rename "jz4740" to just "jz" on the filename and the code? |
| 14:44.51 | larsc | Ayla: usually that's not done, just use the driver as is for the other devices |
| 14:44.52 | *** join/#qi-hardware xiangfu (~xiangfu@fidelio.qi-hardware.com) |
| 14:45.05 | Ayla | really. |
| 14:45.16 | Ayla | ? |
| 14:45.29 | Ayla | so I just copy-paste the code? |
| 14:45.40 | larsc | no |
| 14:46.11 | larsc | keep it as it is and extend it where necessary |
| 14:46.30 | larsc | but don't rename everything |
| 14:48.41 | Ayla | mmmhh |
| 15:18.58 | xiangfu | @tweet QEMU emulated Ben NanoNote http://youtu.be/q6BxbAtJ7F4 |
| 15:19.10 | xiangfu | !tweet QEMU emulated Ben NanoNote http://youtu.be/q6BxbAtJ7F4 |
| 15:19.12 | qi-bot | <PROTECTED> |
| 15:21.02 | qi-bot | おさかな たろう (RT Qi Hardware(1)): RT @qihardware: <xiangfu> QEMU emulated Ben NanoNote http://t.co/FYWEihuQ ( 246992014317604865@qihardware - 2s ago via TweetDeck ) |
| 15:32.25 | whitequark | errr |
| 15:32.37 | whitequark | why qi-bot talks hiragana?! |
| 15:36.18 | *** join/#qi-hardware urandom__ (~user@p548A3926.dip.t-dialin.net) |
| 15:36.40 | *** join/#qi-hardware aisa (~a@c-68-35-162-196.hsd1.nm.comcast.net) |
| 15:37.43 | larsc | why not? |
| 16:51.30 | *** join/#qi-hardware emeb (~ericb@ip72-201-79-123.ph.ph.cox.net) |
| 17:20.06 | 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 |
| 17:20.07 | qi-bot | [commit] Mark Brown: ASoC: core: Fix check before defaulting to regmap (jz-3.5) http://qi-hw.com/p/qi-kernel/82a40fe |
| 17:20.08 | 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 |
| 17:20.09 | qi-bot | [commit] Lars-Peter Clausen: ASoC: jz4740: Use regmap (jz-3.5) http://qi-hw.com/p/qi-kernel/d8b0b5c |
| 17:43.28 | *** join/#qi-hardware heberth (~heberth@186.116.56.250) |
| 17:50.14 | *** join/#qi-hardware viric_ (~viric@unaffiliated/viric) |
| 18:08.43 | *** join/#qi-hardware heberth (~heberth@186.115.109.86) |
| 18:10.38 | *** join/#qi-hardware LunaVorax (~LunaVorax@cau33-2-82-227-183-10.fbx.proxad.net) |
| 19:12.27 | *** join/#qi-hardware heberth (~heberth@190.6.162.167) |
| 19:15.36 | *** join/#qi-hardware jekhor (~jek@leased-line-46-53-195-83.telecom.by) |
| 20:18.02 | *** join/#qi-hardware Textmode (~boneidle@adsl-syd-4-189.ozonline.com.au) |
| 20:32.04 | *** join/#qi-hardware dandon (~dandon@88.151.74.140) |
| 20:36.15 | *** join/#qi-hardware dandon (~dandon@88.151.74.140) |
| 20:41.19 | *** join/#qi-hardware dandon_ (~dandon@88.151.74.140) |
| 20:52.19 | *** join/#qi-hardware jurting (~jurting@ip-128-219-241-92.dialup.ice.net) |
| 21:18.32 | *** join/#qi-hardware GCW2012 (~gcwnow@cpe-76-92-189-100.kc.res.rr.com) |
| 21:18.56 | GCW2012 | anyone with knowledge about ITE IT6610 HDMI |
| 21:19.15 | GCW2012 | or Vivante GC860 GPU |
| 21:45.55 | *** join/#qi-hardware woakas (~woakas@186.28.162.226) |
| 22:03.56 | *** join/#qi-hardware GNUtoo (~gnutoo@arc33-1-78-248-49-133.fbx.proxad.net) |
| 22:30.00 | *** part/#qi-hardware GCW2012 (~gcwnow@cpe-76-92-189-100.kc.res.rr.com) |
| 22:43.39 | *** join/#qi-hardware dandon_ (~dandon@88.151.74.140) |
| 22:50.29 | *** join/#qi-hardware Textmode (~boneidle@adsl-syd-4-189.ozonline.com.au) |
| 23:16.32 | *** join/#qi-hardware Textmode (~boneidle@adsl-syd-4-189.ozonline.com.au) |