Android Question Fast find data in list

[christiaanm]

I would like to search trough a list what contains +1000 items

Dim i As Int

testList.Initialize   

For i = 0 To 2000

    testList.Add("This is test number " & i & " of the list")

Next

and if i press the button it should give the index of the list.
i can't use indexOf because i only know a part of the string, not everyting, for example "ber 20 of"

I tried it with looping trough the list and contain parameter but its really slow.

Sub getListIndex(whatList As List, WhatToFind As String) As Int
Dim i As Int
For i = 0 To whatList.Size -1
    If whatList.Get(i).As(String).ToLowerCase.Contains(WhatToFind.ToLowerCase) = True Then
        Return i
    End If
Next
Return -1
End Sub

is there a way i can do it very quickly, i am not attached to a list and can be any kind of object

Thanks everybody!

 

[Mahares]

is there a way i can do it very quickly

Have you looked at B4XSearchTemplate of XUI Views.

[B4X] XUI Views - Cross platform views and dialogs

XUI Views is a b4x library (https://www.b4x.com/android/forum/threads/100383/#content). The same b4xlib library is compatible with B4A, B4i and B4J It is a collection of custom views and dialogs. Everything is written in B4X. The source code is included inside the b4xlib file, which is a zip...

www.b4x.com

It will be a good choice for what you are trying to do. If you encounter difficulties, post your text file list and come back

 

[ilan]

I would like to search trough a list what contains +1000 items

Dim i As Int

testList.Initialize  

For i = 0 To 2000

    testList.Add("This is test number " & i & " of the list")

Next

and if i press the button it should give the index of the list.
i can't use indexOf because i only know a part of the string, not everyting, for example "ber 20 of"

I tried it with looping trough the list and contain parameter but its really slow.

Sub getListIndex(whatList As List, WhatToFind As String) As Int
Dim i As Int
For i = 0 To whatList.Size -1
    If whatList.Get(i).As(String).ToLowerCase.Contains(WhatToFind.ToLowerCase) = True Then
        Return i
    End If
Next
Return -1
End Sub

is there a way i can do it very quickly, i am not attached to a list and can be any kind of object

Thanks everybody!

maybe using sqlite as your data storage and then using a query to get the string from the db using LIKE. the question is what exactly do you want to do?
why do you need the index of the item? do you want to edit it?

you can also use kvs that uses sqlite but is very similar to maps. (Key->value)

 

[BlueVision]

Do not misunderstand: In general, the way of searching should be oriented towards the database, it is a question of concept. If the data is already stored in an SQL database, that would be perfect. In the worst case, the data itself probably comes from an infinitely large Excel file, which might then also be exported as a CSV file.
An Excel file can be wonderfully imported into a B4X table. It depends on the form of presentation whether the internal search in a B4X table is then sufficient. Importing into an SQL database would perhaps also make sense with a large Excel file if this list does not change often.
A search with strings within a list should be kept as simple as possible. String operations basically cost a lot of time, especially if the arguments to be compared also have to be adjusted before the comparison (upper case / lower case / trimming). The simpler the comparison of two strings is kept, the faster the programme becomes. It may also help to divide into several lists based on certain parameters in order to shorten the length of the lists. These lists have to be generated from somewhere. A list itself is also rather unsuitable for searching if it has to be searched through completely with the search argument. Personally, I only use lists to display search results, not as a source for a search.
The answers and code snippets from Mahares and Ilan show you the way. But for an optimised search, your problem probably requires more information about the source and format of the data. You don't have to give away any data. But for a working concept, it's best to start at the source. Data in the form of a list may not be a good start. But I could be wrong because I don't know your concept.

 

[kimstudio]

At least WhatToFind.ToLowerCase can be taken out of the loop.

 

[emexes]

I tried it with looping trough the list and contain parameter but its really slow.

At least WhatToFind.ToLowerCase can be taken out of the loop.

If it's still too slow, then the next step is to have a parallel List that is already .ToLowerCase, eg Dim testListLowerCase As List

and when you are building (adding to) or updating testList, you do the corresponding for testListLowerCase to keep the two lists in sync

 

[William Lancee]

I am not sure what the problem is, but normally the linear search is very fast, even with .toLowerCase, 1msec for 10000 items.

    Dim aList As List
    aList.Initialize
    For i = 0 To 10000
        aList.Add("abc" & i)
    Next
    Dim markTime As Long = DateTime.Now
    Dim lookFor As String = 5000
    For i = 0 To aList.Size - 1
        Dim s As String = aList.Get(i)
        If s.toLowerCase.Contains(lookFor) Then Exit     'don't forget to exit when found
    Next
    Log(i & TAB & s &  TAB & (DateTime.Now - markTime) & " msec")  '5000    abc5000    1 msec - for 10000 items

 

[JohnJ]

I would like to search trough a list what contains +1000 items

Dim i As Int

testList.Initialize  

For i = 0 To 2000

    testList.Add("This is test number " & i & " of the list")

Next

and if i press the button it should give the index of the list.
i can't use indexOf because i only know a part of the string, not everyting, for example "ber 20 of"

I tried it with looping trough the list and contain parameter but its really slow.

Sub getListIndex(whatList As List, WhatToFind As String) As Int
Dim i As Int
For i = 0 To whatList.Size -1
    If whatList.Get(i).As(String).ToLowerCase.Contains(WhatToFind.ToLowerCase) = True Then
        Return i
    End If
Next
Return -1
End Sub

is there a way i can do it very quickly, i am not attached to a list and can be any kind of object

Thanks everybody!

If your data is sequential you could use a variation of a quick sort

 

[William Lancee]

i only know a part of the string

Binary search or quicksort techniques won't work. But I think that a linear search of lists <100,000 would be OK.
If the list is relatively static, converting the list to lower case first would improve speed somewhat.

The search algorithm in the B4XSearchTemplate indexes the substrings of each item in the list.
This makes indexing CPU intensive but in most cases this is tolerable since it is only done once for a given list.
The indexing makes lookups superfast.

 

[Ricks Film Restoration]

Simple solution: create a Map file from the list. Read the title of each item in the list and put each as Keys in this Map and put the list index as (numeric) Value.
Retrieve the index by using the Map's get function (with the title as input) and then read the contents of the list with the found index.
It works great with multi column lists and I have obtained speeds of 1 msec to find something in a list with over 100.000 items and many columns!
This is much quicker than having to go through the list item by item from top to bottom each time to find what you want.

 

[RB Smissaert]

Simple solution: create a Map file from the list. Read the title of each item in the list and put each as Keys in this Map and put the list index as (numeric) Value.
Retrieve the index by using the Map's get function (with the title as input) and then read the contents of the list with the found index.
It works great with multi column lists and I have obtained speeds of 1 msec to find something in a list with over 100.000 items and many columns!
This is much quicker than having to go through the list item by item from top to bottom each time to find what you want.

Reading the first post of this thread:

>> i only know a part of the string, not everyting, for example "ber 20 of"

and don't think this solution will work.

RBS

 

[stevel05]

but its really slow

Just in case: Do not to test anything for speed in Debug mode.

 

[Ricks Film Restoration]

Reading the first post of this thread:

>> i only know a part of the string, not everyting, for example "ber 20 of"

and don't think this solution will work.

RBS

If the part of the string is unique (so no duplicate entries in the list with the same search string), you could fill the Map with only these partial strings (which could even have variable length). All you need to do is start to search in the Map (with the .containskey function) for the entire string and then gradually shorten the search string by deleting the last character until it is found in the map. You may need a dozen or so iterations to do so, but at about 1 msec per iteration the search will still be very fast.

 

[kimstudio]

Retrieve the index by using the Map's get function (with the title as input) and then read the contents of the list with the found index.

How is the Map.Get() realized internally? I assume it just uses a for-loop to compare every key value until the key is found, so I think faster is doubtful.

 

[Ricks Film Restoration]

Not

How is the Map.Get() realized internally? I assume it just uses a for-loop to compare every key value until the key is found, so I think faster is doubtful.

Not "doubtful" but factual. The Map function seems to use sophisticated indexing techniques, not simple loops. As I told you, it can find an entry in a 100.000 data set in 1 msec. If you search a 100.000 item list from top to bottom it will take hundreds of milliseconds, depending on how far down the searched item is in the list. I know what I am talking about. I have made a personal assistant that responds to about 50,000 questions and it finds the answer in about 1 msec.
You should try what I suggested (and make speed comparisons). You'll be amazed!
Another way is to create a second Map or list that contains the starting index of the first couple of characters. That way you can start the search in the main list not from index=0 but from the index where these characters first appear. Obviously the main list needs to be sorted first.

 

[Erel]

A short tutorial about maps: https://www.b4x.com/android/forum/threads/map-collection-the-most-useful-collection.60304/#content

 

[kimstudio]

Thanks, great to know. I searched map mechanism and seems Map is realized internally by hash table. My understanding is each key is already mapped to a numbered index of an array like structure, so access a key is like to directly access array(keyindex), no search needed, although it may have some overhead in building the map or during put(), with sacrafice of hash algorithm running time or more memory space.

 

[BlueVision]

A short tutorial about maps: https://www.b4x.com/android/forum/threads/map-collection-the-most-useful-collection.60304/#content

Great, see this for the 1st time, damned...

 

[christiaanm]

To end this thread, i used SQLite now (its very quick and very easy) my application works like a charm now!