[Си+GLib] Хочу замутить группировку «таблицы», проясните мне некоторые алгоритмические моменты

Херню ты написал.

Создаешь функцию сравнения строк с учетом полей, строишь одно упорядоченное дерево и выводишь его последовательно.

В чём конкретно херня? Дерево и так будет строиться, вопрос в том, как сделать максимально быструю функцию сравнения, ведь для группировки нужно каждый элемент сравнить с каждым.

Сортируешь по колонкам и усё. Можно выводить в один проход.

Строки: GTree, каждая «строка» является указателем на GTree. То есть, в каждой строке по GTree. Строковые GTree содержат столбцы.

IMO так наиболее быстро будет.

Ничего не понял, меня интересует группировка, как эффективно разбить на группы, и как будет это дело устроено с точки зрения кода. Т.е например есть у вас массив строк, его нужно сгруппировать, как бы вы это делали, как бы вы организовали группировку, при том что вам ведь нужно провести сравнение каждой строки с каждой по очереди, так? Какие средства можно использовать для увеличения скорости этого самого сравнения и как следствия самой группировки? Пытаюсь сформировать представление алгоритма в своей голове :(

> Какие средства можно использовать для увеличения скорости этого самого сравнения и как следствия самой группировки? Пытаюсь сформировать представление алгоритма в своей голове

Бинарные деревья. Они же GTree. При добавлении элементов в дерево автоматически происходит поиск самого оптимального размещения в «дереве». При поиске доступ к нужному элементу происходит всего за несколько итераций (а не через весь массив).

как эффективно разбить на группы

Насколько я понял, тебе надо загнать массив в TreeModel?

# -*- coding: utf-8 -*-
import itertools

data = list(itertools.permutations(['aaa', 'bbb', 'ccc', 'ddd'], 3))

#Сортируем строки по первым двум столбцам
data.sort(key=lambda r:r[:2])

# Как выглядит сортированный массив
for r in data:
    print r

print '\n\n'

# Группировка в один проход по первым двум столбцам
c = [None, None]
level = 0
for r in data:
    for l in (0, 1):
        if c[l] is None or c[l] != r[l]:
            print ' ' * (l*2) + r[l]
            c[l] = r[l]
            level = l + 1
            if l == 0:
                c[1] = None

    print ' ' * (level*2) + r[2]

Массив в TreeModel это частный случай... я наверно в самом начале вообще зашёл не с той стороны, пытаясь объяснить что мне нужно, попытался спросить просто за «некоторую деталь» которая мне не совсем ясна. Если быть точным, я делаю свой DataModel(по типу GtkTreeModel) для хранения данных, естественно, модель должна «уметь» сортировать и группировать свои данные. Данные в модели представлены двумерным массивом(массив указателей), для отображения этих данных планирую строить дерево. В последствии это дерево уже будет рисоваться, создавая «вид». В данный момент как раз занимаюсь алгоритмической стороной организации группировки в модели, т.е как мне сгруппировать данные по какому-либо столбцу? Как сделать это эффективно, ведь данных может быть много(в модели могут быть тысячи записей). Попробую описать алгоритм группировки(для одного столбца, т.е предположим что группировка идёт по одному столбцу): Беру значение первой строки и смотрю, есть это значение среди остальных строк в столбце, если нет, то я создаю новую «группу(добавляю ветку в дерево) и эту запись добавляю в эту группу(создаю ещё одну ветку в дереве и делаю её дочерней той, предыдущей ветки), если же такое значение уже есть, я добавляю его в группу с таким именем. Вот здесь и кроется главный вопрос, ведь как я понимаю, мне придётся сравнивать каждую строчку в столбце со всеми остальными, т.е нужно проверить, входит ли строчка в какую либо группу, если входит, то пропускаем её, если нет, то добавляем её туда. Но тут есть один нюанс - производительность, если записей будет много(скажем сто тысяч), то это поочерёдное сравнение каждой строки со всеми остальными(для выяснения, входит ли строка в группу), будет мягко говоря не айс. Как организовать это дело эффективно? Задавшись этим вопросом, наткнулся на хэш-таблицы(в моём варианте я рассматриваю GHashTable), они вроде как для этого и предназначаются. Тогда можно считать что название группы это ключ, а значение строки это значение ключа, тогда можно будет искать вхождение строки в группу довольно быстро(что-то около O(1)) и проблема производительности вроде как отпадёт. Вот этот момент я никак не могу продумать, что должно быть ключом, что значением, или может, вообще не использовать хэш-функции? Вот тут я как раз и не могу разобраться, каша в голове, если кто может прошу разъяснить...

Ещё момент, конечно можно попытаться использовать готовую модель, ту же GtkTreeModel, но меня интересует велосипед :)

Да... инструментом является Си и GLib, для вида будет GTK+

для отображения этих данных планирую строить дерево.

Принты замени на создание новых узлов и всё.

Хм... т.е если сразу список строк отсортировать, то никакая хэш-таблица и не понадобиться и всё будет в один проход? Супер, спасибо :)