0

I have a Gtk.TreeView with a custom model (inheriting from Gtk.TreeModel) and I show ~150K rows. I'm using PyGtk, but it should not matter that much.

The GUI interaction is ok, but when activating interactive-search, it takes forever (~10sec per char). From what I understood from Searching a ListStore and tested, the interactive-search checks each row of the ListStore (internally stored as linked-list) to find the value.

Since I am searching a sorted column, I want to do binary search.

How can I do that ? Do I need to re-program the interactive-search from scratch ? Can TreeModelSort be useful ? (I do not get how its internals are managed)

If I roll my own search UI, I'm not sure how to start. A sketch looks like that :

  1. Disable built-in interactive search
  2. Create a search UI, and connect it to the right keypress
  3. Manually do a binary search in my custom representation of the data (or in the sorted shown rows if random access is possible)
  4. Select the correct match.

For 3. it seems from GtkTreeModel that have a random access to rows:

A gtk.TreeModel object supports some of the Python Mapping protocol that allows you to retrieve a gtk.TreeModelRow object representing a row in the model.

Is it truly and efficiently random access ?

Community
  • 1
  • 1
Bastien Jacquet
  • 182
  • 7

1 Answers1

0

It is unclear exactly how you are implementing the custom gtk.TreeModel - is it a ListStore, or something you roll on your own? Even with 150K rows, it is not clear that searching a list store would take 10 seconds.

It is possible to implement binary search on a ListStore, but the search implemented by TreeView is not binary, it simply scans the list from the current position to the end, looking for a match. It allows customizing the "equals" callback, but not the search strategy. What you need is a more general search function that accepts a key and returns the corresponding position in the tree.

To implement efficient searching of large trees, you will need to roll your own search UI, along the lines of what you outlined in the edit to your question. Looking at the existing implementation, it is not much work: it boils down to showing a top-level gtk.WINDOW_POPUP window that contains an entry whose activate signal is connected to code that does search and positions the tree cursor to the row it found.

user4815162342
  • 141,790
  • 18
  • 296
  • 355
  • I edited the question to be clearer: it seems to me that TreeModel implement random access, but I'm puzzled as the underlying TreeStore dont. What is the truth ? – Bastien Jacquet Nov 12 '14 at 19:13
  • @BastienJacquet Note that `TreeModel` is the interface, and `TreeStore` and `ListStore` are its concrete implementations, of which you are using the latter. `ListStore` is not a linked list, it is implemented using a `GSequence`, which is internally a tree that exposes a sequence API. `GSequence` (and consequently `ListStore` is designed to scale, enabling `O(log n)` insertion anywhere in the list, as well as `O(log n)` random access. This means that it actually *is* possible to implement binary search using a `ListStore`, with the expected complexity of `O(log^2 n)`. – user4815162342 Nov 13 '14 at 18:54