Page 1 of 2
The fastest to search: list or array ? [SOLVED]
Posted: Fri Apr 04, 2014 4:20 pm
by 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.
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 5:12 pm
by 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
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 5:14 pm
by 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
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 5:48 pm
by 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
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 5:49 pm
by 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)...
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 5:57 pm
by 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
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 6:00 pm
by 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.
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 6:20 pm
by Klaus
atout66 wrote: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
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 6:23 pm
by atout66
Never mind
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 8:06 pm
by rkriesel
atout66 wrote:
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
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 8:17 pm
by 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
Re: The fastest to search: list or array ?
Posted: Fri Apr 04, 2014 8:27 pm
by Simon
Hi atout66 ,
put the millisec into startTime
--do you lineOffset or repeat or ...
answer the millisec - startTime
Simon
Re: The fastest to search: list or array ?
Posted: Mon Apr 07, 2014 3:14 pm
by 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.
Re: The fastest to search: list or array ?
Posted: Mon Apr 07, 2014 4:52 pm
by 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
Re: The fastest to search: list or array ?
Posted: Tue Apr 08, 2014 11:48 am
by MaxV
atout66 wrote: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