 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : Need Some Sort Ideas
  Page 2 of 2 |
|||||
| Author | Message | ||||
| factus10 Regular Member  Joined: 30/12/2014 Location: United StatesPosts: 45 |
Const NUM=100
Dim integer a(NUM+1) Dim integer x(1010) Dim t Randomize Timer For t=1 To NUM a(t)=Int(1000*Rnd()) x(a(t))=a(t) 'variable x(num) is given the value num Print a(t), Next t Paul, I see what you're doing here: you're using an associative array. The sort happens by way of the underlying organization of the array. This only works if there are no duplicates in data because you can't have duplicate keys. It's interesting. I'd have to refresh my memory on sorts but this is unique to my memory. David |
||||
| Dylan Regular Member Joined: 17/06/2013 Location: NetherlandsPosts: 81 |
MicroBlocks already mentioned Merge Sort in post 4. See https://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives for how to use it with tapes. |
||||
| Dylan Regular Member Joined: 17/06/2013 Location: NetherlandsPosts: 81 |
It is not a way of sorting. It does list all values, but you asked me to sort die-rolls of "4 5 5 2 6 2" and I told you "2 4 5 6" you probably wouldn't be very happy. There is a story in Programming Pearls by Jon Bentley where the challenge is to sort several million 7 (decimal) digit numbers using only two megabytes of memory. But storing numbers from 0 to 9999999 takes 24 bits, or 3 bytes, so storing a million of them takes three megabytes, and we only have two and that's not even enough for the first million, never mind the others. Until it turned out that all the numbers were unique telephone numbers, which meant that a single bit could store whether it existed or not. Anyway, when you know you have small integers only, then using these as an index into an array is called https://en.wikipedia.org/wiki/Counting_sort and was invented in 1954 (about 17 years before you devised), but you have to count how many of them you have, not just whether you have them, unless - as in Bentley's case - they are guarantueed to be unique. |
||||
MicroBlocks Guru  Joined: 12/05/2012 Location: ThailandPosts: 2209 |
There are other interesting options and that is for instance using a linked list. If the data in FRAM is fixed length then that would make it even easier, but is not required. With each record you add two pointers, one to the previous record and one to the next record. You can then even add a record and put it in the right place by using these pointers. For sorting it is pretty easy. You read the first record and set previous to -1 and next to -2.(-1 and -2 are special cases and -1 would mean that this is the first record in the list and -2 would mean it is the last recod in the list) [code] [record 0 data][prev=-1][next=-2] [/code] The second record is then compared with the first and if it is smaller then you set previous of the second record to -1 and next to 0. You then adjust the first record's previous pointer to 1. etc.. [code] [record 0 data][prev=1][next=-2] [record 1 data][prev=-1][next=0] [/code] You need to keep track which record will be the first so that you now where the lists starts. Keeping track of the last is also handy to have. Another option that might fit in memory is to only have an index in memory. For 2000 records it would take 8K with some tricks that can be 4K. You create an index array I(2000) and fill them with 0-1999. You then do any kind of sort you want but instead of using the array for data you use the array to give you a pointer to the data. When comparing two values you use I(x) and I(y) not directly but use the values contained in them to retrieve the info from FRAM. I(x) and I(y) would give you two numbers, lets say 0 and 1. You then retrieve record 0 from FRAM and record 1 from FRAM. Compare these values and if you need to swap them you swap not the data in FRAM but you swap the entries in the array. Microblocks. Build with logic. |
||||
| Dylan Regular Member Joined: 17/06/2013 Location: NetherlandsPosts: 81 |
Typo 17 should be 27 in my previous post lol. |
||||
Justplayin Guru Joined: 31/01/2014 Location: United StatesPosts: 327 |
I am basically already treating the FRAM as an array (at least in my mind). Simple math of take the element number and multiply it by the record length (59). Element 0 would be FRAM address 0, Element 1 is Address 59... Element 2000 is address 118000. Uing this, I have so far tried Bubble sort, Selection sort and Comb sort. The Comb sort took 9 minutes 15 seconds for 2000 records. Personally I think that is pretty good for a Micromite, but not good enough for my application. Oddly enough, the numbers I'm sorting are telephone numbers. [LOL] I don't know about the rest of the world, phone numbers in the USA are 10 digits, excluding the country code (long distance code)which is rarely used anymore. However the caller-id system allows for up to 15 digits. @MicroBlocks - You have some great ideas! But... I have to consider even 4K as too much memory. I already know this whole application is short on RAM from the start since most of it will be the Mik-Matrix display software which current uses almost all of the a 170s RAM. Okay, this is what I'm building... The whole reason I got evolved with the Mik-Matrix displays was to produce a easy to read Caller-ID display. What I'm going to do is display the caller ID info in color based on the number being known and allowed (Green), known and undesired (Red) or unknown (Yellow). When a call comes in the Caller-ID info is looked up to determine how the info should be displayed. This lookup process needs to be VERY fast, so the data will be loosely indexed. Those numbers not found are added to ring buffer call log. The call log entries may be reviewed, edited later, categorized and added into the main caller data (if desired). As mentioned before, I am leaning toward having a one Micromite handle just the data and another to drive the display. I have a couple of SkinnyMites which need a home a this project might be it (more memory and more speed). Of course, there is always the option to have the sort scheduled to occur at like 3AM for 10 minutes, which would not be too bad for personal use. --Curtis I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
| MicroBlocks Guru Joined: 12/05/2012 Location: ThailandPosts: 2209 |
I see what you are doing. The fastest way to get a unique number is to do a lookup from right to left. Did you try to just do the lookup directly from FRAM, even when it is not sorted. Might take 0.1 second. Then no sorting have to be done. I think if you can retrieve it within a single ringing cycle it would be fast enough as first after the first ring people have to respond by stopping what they do. This will give you at least 0.5 seconds. Might be more than enough. Microblocks. Build with logic. |
||||
| factus10 Regular Member Joined: 30/12/2014 Location: United StatesPosts: 45 |
Curtis, It sounds like you need to sort the data only once. Instead of trying to sort the data after appending numbers to your list, you might want to consider spacing out your initial data set with at least one blank record between each phone number and inserting into the blank. You could then trigger a process that re-gaps the data when the phone is not ringing. The process would need to create space from the bottom up, assuming you've started your data at the base memory address. And it wouldn't be too difficult to make the process interruptible, so if the phone rings in the middle, it could just be suspended. Another thought to consider is positioning your list in the middle of your FRAM. Then your re-gap process could work in both directions. David |
||||
vegipete Guru Joined: 29/01/2013 Location: CanadaPosts: 1129 |
I think MicroBlocks' suggestion with a linked list should be pursued. Look up binary trees. If you bump each record to 64 bytes, you'll have room for the 2 pointers per record. One pointer points to the next record that is smaller, the other pointer to the next record that is higher. This linked list forms a tree, starting from the trunk. A given pointer for any record is 'zero' if there is no record in that direction. For example, the first record starts the trunk of the tree. Both pointers are set to zero. The next record to be added is compared to the trunk. If, for example, this new one is greater, the pointer to the bigger record is examined. Since it is zero, we've hit the end of the tree and the correct spot in the tree has been found. Thus the higher pointer of the previous record is changed to point to this new record and both pointers of this new record are set to zero. This same process allows each new record to be quickly added to the tree. There is however one hazard that must be accounted for. Searches are fast (of the order log(n) I believe) as long as the tree is balanced. But real data probably won't balance nicely. So it is necessary to 'balance the tree' from time to time. Visit Vegipete's *Mite Library for cool programs. |
||||
| Justplayin Guru Joined: 31/01/2014 Location: United StatesPosts: 327 |
I've figured it out! No sort is needed... at least not of the main caller data. It's already sorted, so I simply need to sort the new records to be added then open up the spaces to insert them. If I want to add 5 new records I start at the end of the list and bump everything down five record spaces until I find the spot to insert the largest new record. Then continue by bumping everything down 4 records then insert the next largest record. Repeating this until all the new records are inserted into their proper places. Everything essentially done in one pass. The way I see it, after the initial flood of new start up data, the number of records added at one time will probably be pretty small. So, this method should be pretty quick. Basically this is David's (factus10) idea without trying to manage the gap space between all the different groups. --Curtis I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
| Page 2 of 2 |
|||||
 Print this page |
 |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |
