BEst way to search QList for item

[Michiel]

The most (and least) efficient way to search for a value in an unsorted list is to just cycle through it, yes.

If you do this very often in your application, you may still want to switch to a hash or tree structure.

[TheRonin]

Why not just sort the list? If the order of the items in your list is irrelevant but they still have some unique and sortable property, implementing a sorting algorithm on top of the work you've already done might speed things up considerably.

[jh]

i have a similar problem:

consider a string list. i search for any strings which match a certain pattern,
e.g *abc*. a QHash doesn't help here, sorting doesn't help neither.
how can i find any matching items efficiently?
where can i read about this kind of problem, any good literature?

best regards,
jh

[TheRonin]

i have a similar problem:

consider a string list. i search for any strings which match a certain pattern,
e.g *abc*. a QHash doesn't help here, sorting doesn't help neither.
how can i find any matching items efficiently?
where can i read about this kind of problem, any good literature?

best regards,
jh

I think the easiest solution means you're stuck searching linearly through the list.

[Michiel]

I think the easiest solution means you're stuck searching linearly through the list.

The easiest, to be sure. There might be a better way, depending on the pattern you want to search for. If, for example, it's always something like: x* (begins with x) you could still branch on the prefix of the strings. Same thing with *x (ends with x). *x* (contains x), though, would make things a bit more difficult. Except if x is always a fixed distance from the beginning or the end of the string.

If you want to search with a variable pattern, you haven't got a hope.

[kroenecker]

I say change the object in the class to a hash and, if it was properly implemented in the first place, you already have a wrapper used to actually access the values in the QList. Now simply rewrite it so that you are utilizing the QHash. Otherwise, write a simple ruby/perl script that goes through all your code and replaces the proper values.

This is the only decent way to approach the problem.

[^NyAw^]

Hi,

I think that a good way to do this is to have the QList sorted by your QString (inserting intems have to be performed manually moving the other items). Then you could try a "dicotomic search" that takes the middle of the QList, compare the values, if the value is minor than the value in the list, you have to get the [0 .. middle-1] QList and do it again until you find th item. If the value is major than the value in the middle of the QList you will take the [middle-1 .. MAX_LIST].

The way to get the QList sorted can be performed by inserting the items sorted when you create them and moving the rest of the objects, or you can perform a sort algoritm like "insertion method", "bubble method", "selection method", ... (I don't know if these are the correct names in english).

I hope it will help you,

[Michiel]

Why not just sort the list? If the order of the items in your list is irrelevant but they still have some unique and sortable property, implementing a sorting algorithm on top of the work you've already done might speed things up considerably.

Because at best, sorting is done in O(n log n). Searching for a value in an unsorted list is still only O(n).

Perhaps keeping a list sorted at all times by inserting values only in the right location would be different. Then you could use a binary search algorithm, at O(log n). However, inserting a new value would jump from O(1) to O(log n).

[TheRonin]

Then it seems that keeping the list sorted at all times is the way to go, provided insertions are performed far less frequently than searches.