The fastest to search: list or array ? [SOLVED]

[atout66]

Hi to all,
As said in the title of this topic, I'm wondering what is the fastest to make a text search.
Consider these two hypotheses:
1- A list of 25000 lines, each line has 11 items
2- An array of 25000 rows and 11 colums

Problems:
1 - I want to search a word (as item 1), let say near the line or row 22000.
2 - From that word, I want to get the item or colum number 9.

I suppose the list will be slower in Problem 2, but faster in Problem 1, right ?

Kind regards.

[dunbarx]

Hmmm.

How does one search an array directly? I may be missing a big piece of my LC knowledge, but if I am right, you would have to change your array variable in the clear anyway, and then the question is moot.

Do I have a big hole or not? Anyone?

Craig

[Klaus]

Bonjour atout66,

no idea what is faster, but you can do:

Code: Select all

...
put fld "the long list with many items" into tList
put "Whatever" into tSearchWord
put lineoffset(tSearchword,tList) into tLine
## Not found!
if tLine = 0 then 
  exit to top
end if
put item 9 of line tLine of tList int tFoundItem
...

Best

Klaus

[dunbarx]

Klaus' reply and mine crossed in the email.

He implies that the search is to be made on ordinary, not array, variables, and that the search is very fast. He is right about the speed. Still waiting to see if anyone has searched an array from within that array.

But does all this answer your question? I assume you can use the itemOffset within what Klaus gave you to get this going.

Craig

[atout66]

Thanks to all of you for your responses.
Does the lineOffset() in your code, Klaus, use a logarithm research, or does it scan every occurence, step by step (longer!) ?
The first items of each line are all alphabetiques and sorted by ascending order, that's why I care on a logarithm research (faster)...

[dunbarx]

Hi.

Do you mean a "binary" search?

Anyway, on a long list, the "lineOffset" is about three times faster than a repeat for each... loop. At least for a list of 25,000 lines with a dozen items in each line (7 mS vs. 20 mS). Both very fast, though. You would not see the difference

Craig

[atout66]

Craig, for sure, I will try the Klaus's proposal as I'm learning LC recently.
All your contributions are very usefull to me.
I could never progress so well without your help at all.

[Klaus]

Does the lineOffset() in your code, Klaus, use a logarithm research, or does it scan every occurence, step by step (longer!) ?
The first items of each line are all alphabetiques and sorted by ascending order, that's why I care on a logarithm research (faster)...

Sorry, i have no idea what is going on in the engine

[atout66]

Never mind

[rkriesel]

Problems:
1 - I want to search a word (as item 1), let say near the line or row 22000.
2 - From that word, I want to get the item or colum number 9.

Here's a approach using an array, so you can compare timings for techniques.

Code: Select all

local sLineForWord

on setup
    repeat for each line tLine in field "myField"
        put tLine into sLineForWord[ word 1 of tLine ]
    end repeat
end setup

function getItem9ForWord pWord
    return item 9 of sLineForWord[ pWord ]
end getItem9ForWord

If you compare the timings, please post your findings.

-- Dick

[atout66]

OK Dick, no problem.
I'll let you know my experiments when the matrix will be sufficiently large.
For now, I precisely try to develop a system clock that records the time but I'm not really cleaver at it and that's why I'm going to post an other topic right now

[Simon]

Hi atout66 ,

put the millisec into startTime
--do you lineOffset or repeat or ...
answer the millisec - startTime

Simon

[MaxV]

Why don't you use the sqlite included in Livecode?
Database is good when you search data and you need to do it quickly.

[atout66]

You're right MaxV, I thought about sqlite, but I didn't spend time to learn about it for the moment.
It's an open option to me

[MaxV]

You're right MaxV, I thought about sqlite, but I didn't spend time to learn about it for the moment.
It's an open option to me

This page cover the essential: http://livecode.wikia.com/wiki/SQLite