Hello. There is an application in which you need to display the tv program in epg format

enter image description here

The right part is the channels, the left is the program. The whole thing is done through the drawing in the class inherited from the View. The channels are stored as

List<String Name,List<Program>>>

Here it is necessary to organize an instant search by channels. Now the idea is this. I can sort through the List of channels with the character entered. But I don’t like this idea. Let's say 1000 channels, enter 4 letters and it turns out I need to sort the List 4 times in 1000. Who knows how will make such a search?

    2 answers 2

    I think the prefix tree is well applicable to this problem.
    It looks like this:

    enter image description here

    This is a tree, associative array . Keys are strings, and values ​​are arbitrary. Each leaf of the tree contains a value, and the edges store lines.
    If we go down from the root along the edges to the sheet, combining the lines on the passed edges, we will get the original line - the key for which the value is stored.

    The complexity of the search will be linear from the length of the string - the key.

    It seems to me, in your case, the size of the channel list is small enough for the usual search in the list to work quickly (the number of channels is unlikely to be in tens of thousands) and the problem is rather that the search will be performed more often than necessary. In this case, you just need to add a user input delay to start searching through channels not immediately after entering one character, but to postpone this task, say, 700 milliseconds, thereby giving the user time to enter more characters and send a search request over several characters entered.

    I assume you are using TextWatcher to respond to user input. The easiest solution to do this is with the Handler class.

     private Runnable delayedFiltering = null; @Override public void afterTextChanged(Editable input) { if (delayedFiltering != null) { getHandler().removeCallbacks(delayedFiltering); } delayedFiltering = new Runnable() { @Override public void run() { performFiltering(input.toString()); } } getHandler().postDelayed(delayedFiltering, 700); }

    You can create a separate HandlerThread or simply use the getHandler method of your TextView . The main removeCallbacksAndMessages(null) in no case do not use removeCallbacksAndMessages(null) in the second case.

    Instead of creating a new anonymous Runnable each time, you can create your own class that implements this interface, add a search field to it and update this value instead of creating a new Runnable

     private class DelayedFilter implements Runnable { private String constraint; @Override public void run() { performFiltering(constraint); } } private DelayedFilter delayedFiltering = new DelayedFilter(); @Override public void afterTextChanged(Editable input) { if (delayedFiltering != null) { getHandler().removeCallbacks(delayedFiltering); } delayedFiltering.constraint = input.toString(); getHandler().postDelayed(delayedFiltering, 700); }

    If you are familiar with reactive programming, then the same can be done using the RxJava and RxAndroid libraries. Sample code using the debounce method is here.

    • Why some time delays, it is absolutely not effective and does not solve the problem of entering several characters, maybe the user has decided to dig deeper in the nose .. why not just start filtering after entering a certain number of characters (for example, 3-ex), as is done in all normal input filters - pavlofff
    • It does not interfere. The same will begin after entering the fourth, fifth and subsequent characters. - Agrgg