OpenEuphoria

2. Re: 20gigabyte string searching

• Posted by cklester <cklester at yahoo.com> Oct 02, 2004
• 465 views

Kat wrote:
> 
> Serious question: what's the best way to search twenty gigabytes of text for 
> a 100byte substring, using Euphoria?

Would it be easier to create an index (like a b-tree or something),
then use that for searching?

-=ck
"Programming in a state of EUPHORIA."
http://www.cklester.com/euphoria/

4. Re: 20gigabyte string searching

• Posted by cklester <cklester at yahoo.com> Oct 02, 2004
• 477 views

People wrote:

> > > Serious question: what's the best way to search twenty gigabytes of text
> > > for a
> > > 100byte substring, using Euphoria?
> > Would it be easier to create an index (like a b-tree or something),
> > then use that for searching?
> Sure! Where? 
> 20gig in a index in an Eu sequence is 80gigs.

I mean like this:

{ "This", "Is an example", "Might not be", "Accurate" }

Index would be:

{
 {"A", {4}},
 {"B", {}},
...
 {"I", {2}},
...
 {"M", {3}},
...
 {"T", {1}}
}

So if you search for "Might not be," it searches the index first for 'M',
finds all instances in the list where the searchable items start with 'M'
and finds one at 3, then just test the rest.

Or, even an index like this:

{ "T", "IAE", "MNB", "A" }

So if I search for "is an example," it looks for the first-letter-of-each-
word pattern of "IAE" and finds it.

Either one of these methods will reduce the required storage for a
regular index of words, plus it will speed up the searches significantly.
I think. I could be wrong. It's late. :)

-=ck
"Programming in a state of EUPHORIA."
http://www.cklester.com/euphoria/

6. Re: 20gigabyte string searching

• Posted by Derek Parnell <ddparnell at bigpond.com> Oct 02, 2004
• 478 views

Kat wrote:
> 
> Serious question: what's the best way to search twenty gigabytes of text for 
> a 100byte substring, using Euphoria? Keep in mind Eu will blow up 20gigs to 
> 80 in ram, and each copy made to munge it is another 80 gigs, so loading 
> the file into a sequence isn't possible. I foresee tons of disk thrashing, as
> i
> don't have gigs of ram laying around..
> 
> The two gigs can be formed like this:
> {"string-1","string-2"...."string-n"}
> where each string-x is 20 to 120 chars long, most will be in the 100 
> character neighborhood. Chances of them being sorted is low, as i don't see 
> how Eu can be used to sort them in my lifetime.
> or they can be like this:
> {string-1\nstring-2\nstring3\n...string-n}
> 
> I have a list of 150 million string-xs laying here, and don't know the best
> way
> to put them together so solve the search problem. Flat sequence with 
> separators, or nested sequence? Having a parallel sequence of what was 
> found would be terribly nice, but would be equally huge in count (altho 
> shouldn't be as big absolutely).

I guess I don't understand your situation, but why do you need to have 
the whole 20Gigs in RAM at once. I just did a test and I can do a brute-
force string search over 20Gigs in about 70 minutes, using no more
than a meg of RAM.

Anyhow, if you've got the disk space you can index things a lot. This is
basic stuff for databases. You might need about 40-60Gigs to index the
words, but will speed up searching 100-1000 times.

-- 
Derek Parnell
Melbourne, Australia

8. Re: 20gigabyte string searching

• Posted by Terry Constant <EUforum at terryconstant.com> Oct 02, 2004
• 447 views

Kat,

One other thought. You mentioned that 20 gb of text becomes 80 gb
as a sequence. If size is a major issue, consider using regular
expressions. If the data you are searching remains as a single string
of text data, you will not have the size increase you mention.

Karl Bochert submitted regex.zip 2002-04-23. I have used his routines
some and they are quite usable.

In short, using regular expressions on single large strings could 
help with the size issues.


Terry Constant

10. Re: 20gigabyte string searching

• Posted by Pete Lomax <petelomax at blueyonder.co.uk> Oct 03, 2004
• 440 views

On Sat,  2 Oct 2004 22:26:26 +0000, Mike <vulcan at win.co.nz> wrote:

>Depending on the hash table quality there might be, say, 2 or 3 
>disk movements per URL search.
>
>Mike
>
>PS: This idea seems similar to the one Pete posted but the index is 
>managed in RAM so performance should be much better (at the expense of 
>huge amounts of RAM).

I thought about that, with a hash table of a million entries on disk,
and 15 million urls, if the hash function does its job, the average
bucket size will be 15. Either way, (15 or 2) local disk accesses will
probably be faster than reading a 100-byte url from the interweb.

Pete

12. Re: 20gigabyte string searching

• Posted by jiri babor <jbabor at paradise.net.nz> Oct 04, 2004
• 465 views

Kat, my Euphoria is a bit rusty, I have not touch it for almost two years, but
you might be interested in following code.
Let me know if you are, in principle, because a number of substantial
optimizations is still possible.

jiri

--  kat.ex : version 1.00
--  jiri babor
--  jbabor at paradise.net.nz
--  04-10-04

include file.e                          -- dir    

function search(sequence s, object key)
    --  binary search of sorted sequence
    --  return {flag, index}, where
    --      if flag = 1 ... key found at index 
    --      if flag = 0 ... key not found, index is insertion point

    integer c,hi,lo,mid

    lo = 1
    hi = length(s)

    while lo <= hi do
        mid = floor((lo + hi) / 2)
        c = compare(key, s[mid])
        if    c < 0 then                -- key < s[mid]
            hi = mid - 1
        elsif c > 0 then                -- key > s[mid]
            lo = mid + 1
        else                            -- key = s[mid]
            return {1,mid}
        end if
    end while

    return {0,lo}
end function

function pword(integer n)               -- pseudo word: random ASCII string 
    sequence w

    w = {}
    for j = 1 to rand(n) do
        w &= rand(26)+96
    end for
    return w
end function

procedure hoard(sequence path, integer rid, sequence params, integer maxn)
    --  path: data directory
    --  rid: routine_id of function returning next address
    --  params: parameter sequence of rid
    --  maximum number of addresses held in single file

    object a,x
    sequence data,last,lasts,name,names,newname,r
    integer count,f,f1,f2,hits,m,m1,n,r2

    count = 0                           -- address counter
    hits = 0                            -- address collision counter

    if path[length(path)] != '\\' then
        path &= '\\'
    end if

    x = dir(path)
    if atom(x) then
        puts(1,"Error: data directory does not exist. Aborting...\n")
        abort(1)
    else
        names = {}
        lasts = {}

        f1 = open(path & "names","r")
        f2 = open(path & "lasts","r")

        if f1 != -1 then                -- initialized database
            while 1 do
                x = gets(f1)
                if atom(x) then exit end if
                x = x[1..length(x)-1]   -- strip '\n'
                names = append(names, x)
            end while
            close(f1)

            lasts = {}
            while 1 do
                x = gets(f2)
                if atom(x) then exit end if
                x = x[1..length(x)-1]   -- strip '\n'
                lasts = append(lasts, x)
            end while
            close(f2)
        end if
        n = length(names)
    end if

    -- main loop
    while get_key() != 27 do            -- esc
        a = call_func(rid,params)
        count += 1
        r = search(lasts, a)
        r2 = r[2]
        if not r[1] then                -- not found among last addresses
if r2 > n then              -- address > last address of last data
            file
                if n = 0 then           -- no data files yet
                    n = 1
                    name = "1"          -- new file name
                    f = open(path & name, "w")
                    puts(f, a & '\n')
                    close(f)
                    names = append(names, name)
                    lasts = append(lasts, a)
                else                    -- append the last data file
                    name = names[n]
                    f = open(path & name, "a")
                    puts(f, a & '\n')
                    close(f)
                    lasts[n] = a
                end if
            else
                name = names[r2]
                data = {}
                f = open(path & name, "r")
                while 1 do
                    x = gets(f)
                    if atom(x) then exit end if
                    x = x[1..length(x)-1]   -- strip '\n'
                    data = append(data, x)
                end while
                close(f)
                r = search(data, a)
                if r[1] = 0 then        -- not found: insert
                    data = data[1..r[2]-1] & {a} & data[r[2]..length(data)]
                    -- write it out
                    m = length(data)
                    if m > maxn then    -- subdivide
                        m1 = floor(m/2)
                        newname = sprint(n+1)
                        names = names[1..r2-1] & {newname} & names[r2..n]
                        last = data[m1]
                        lasts = lasts[1..r2-1] & {last} & lasts[r2..n]
                        n += 1
                        f = open(path & newname, "w")
                        for i = 1 to m1 do
                            puts(f, data[i] & '\n')
                        end for
                        close(f)
                        data = data[m1+1..m]
                    end if
                    f = open(path & name, "w")
                    for i = 1 to length(data) do
                        puts(f, data[i] & '\n')
                    end for
                    close(f)
                else
                    hits += 1
                end if
            end if
        else
            hits += 1
        end if
    end while

    -- save control sequences
    f1 = open(path & "names", "w")
    for i = 1 to length(names) do
        puts(f1, names[i] & '\n')
    end for
    close(f1)
    f2 = open(path & "lasts", "w")
    for i = 1 to length(lasts) do
        puts(f2, lasts[i] & '\n')
    end for
    close(f2)

    printf(1, "%d addresses\n", count)
    printf(1, "%d collisions\n", hits)
end procedure

hoard("c:\\data", routine_id("pword"), {4}, 100)