Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

[REBOL] Re: [algo] Intervals and parsing

From: tomc:darkwing:uoregon at: 12-Mar-2004 0:10

On Thu, 11 Mar 2004, Didec wrote:
> [algo] Intervals and parsing > Hi all, > > For one of my apps, I have to manage a very long list of integer! > I need to know if an integer! is in the list, and i need to add it to the list. > > To avoid an infinite block of integer! that will overflow the memory for nothing, and considering the fact that most of the values will follow themselve, > I use an intervals dialect and some funcs. > > The values are stored in a block, but consecutives values are replaced by first and last values separate by a minus sign "-". > > I.e. : [0 1 2 3 4 5 10 11 12 13 15 19 20 21 22] > become [0 - 5 10 - 13 15 19 - 22] > > I use 2 functions, one to check if a value exists in list, and one to add the value to the list. > > I post the funcs here for 2 reasons : > 1) Maybe someone would need it > 2) Maybe someone can do better or simpler > > Anyway, comments are welcome > > DideC >
Hi DideC, as much as I do like parse I am unconvinced it is the ideal solution for managing a list of integers. I changed your interval datastructure to be a list of pairs!, each representing an interval, and used binary search instead of parse to locate solutions/insertion-points. it has not been tested beyond a few runs of your automatic testing and it is incomplete as it does not merge adjecent intervals when they meet. but I would be curious as to how it fairs in comparison to the parse version on your large data sets. --- script --- REBOL [ Title: "binary interval search on pairs" Author: "Tom Conlin" Date: 2004-Mar-11 Version: 0.0.1 File: %binary-interval-search.r Purpose: {DideC: I have to manage a very long list of integer! I need to know if an integer! is in the list, and i need to add it to the list. To avoid an infinite block of integer! that will overflow the memory for nothing, and considering the fact that most of the values will follow, I use an intervals dialect and some funcs. The values are stored in a block, but consecutives values are replaced by first and last values separate by a minus sign "-". I.e. : [0 1 2 3 4 5 10 11 12 13 15 19 20 21 22] become [0 - 5 10 - 13 15 19 - 22] I use 2 functions, one to check if a value exists in list, and one to add the value to the list. } Comment: {} History: [] ] ;;; adapted from ;;; http://www.rebol.org/cgi-bin/cgiwrap/rebol/download-a-script.r?script-name=binary-search.r binary-interval-search: func [ interval[block!] {smaller to bigger sequence of disjoint pairs} key [integer!] "integer to find in the intervals" /local lo mid hi tmp ][ lo: 1 hi: length? interval if hi <= lo [return 0] mid: to-integer (hi / 2) while[hi >= lo][ tmp: pick interval mid either (key >= tmp/1) and (key <= tmp/2) [return mid] [either key > tmp/2 [lo: mid + 1][hi: mid - 1]] mid: to-integer (lo + ((hi - lo) / 2)) ] mid ] intervals: context[ where: 1 included?: func[interval [block!] value [integer!]][ where: binary-interval-search interval value ;true all[not zero? where value >= interval/:where/1 value <interval/:where/2] ] include: func[interval [block!] value [integer!] /local here][ if included? interval value[return] here: at interval where either tail? here[insert here 1x1 * value] [;print [value 'found first here 'at where] either value > here/1/2 [either 1 + here/1/2 = value [here/1/2: value] [here: next here either all [not tail? here -1 + here/1/1 value] [here/1/1: value] [insert here 1x1 * value] ] ] [either -1 + here/1/1 = value [here/1/1: value] [here: back here either 1 + here/1/2 = value [here/1/2: value] [insert here 1x1 * value] ] ] ] ;;; mearging adjecent pairs is left as an exercise ] ] ;;;;;;;;;;;;;;;;;;;;;;;; it: [-1x-1 1x1 4x5 7x10 12x12 20x22 30x30 ] ii: func [val] [ prin intervals/included? it val prin " " probe intervals/interval/where ] ato: func [val /local it2] [ intervals/include it2: copy it val probe head it2 ] ;***** Some automatic Tests random/seed now/time/precise i: copy [] test1: does [ print "--- Test1 : includes values ---" loop 50 [intervals/include i v: random 40 print [v "->" mold i]] ask "Press enter to continue" print "^/" ] test2: does [ print "--- Test2 : check if values are included?---" probe i loop 50 [print [v: (random 50) - 5 "?" either intervals/included? i v ["yes"][" no"]]] ask "Press enter to continue" print "^/" ] test1 test2 print {Type "test1" or "test2" to redo a test} halt