LINUX.ORG.RU

Библиотека алгоритмов и структур данных для C

 , ,


0

4

В который раз наблюдая за велосипедами в одном сишном проекте, задался вопросом, а нет ли относительно «стандартной» библиотеки для алгоритмов и структур данных, хотя бы на уровне крестовой STL?

И даже если есть, то почему почти в каждом проекте(возьмем для простоты открытые) свои велосипеды? На каждый чих. Неужели язык толкает на это(сложно предложить достаточно общее решение)?

Если такой библиотеки просто нет, то возможно есть смысл ее создать? У кого какие мысли, кто какие перспективные разработки знает?

И да, я в курсе существования glibc, queue.h и tree.h, коллекций в glib и пр.

Есть еще какие-то sglib, gdsl. Но их не использовал и их использование не видел.


Ответ на: комментарий от TsarC

Понимаешь в чем штука - идеология гнутого кода такая - я пишу код и я не хочу, чтобы мои труды пошли на анальную проприетарщину.

Спасибо, я понимаю идеологию. И не имею ничего против.

С чего ты требуешь от пацанов, чтобы они тебе давали свой код?

Я ничего не требую.

Право юзать тебе никто её не давал

Для этого есть другие лицензии.

Пиши свой - плати бабки.

Ну да, так и делают.

amazpyel ★★★ ()
Последнее исправление: amazpyel (всего исправлений: 2)
Ответ на: комментарий от TsarC

и да, можешь мне показать софт, который под лицензией GPL и который продается?

amazpyel ★★★ ()
Ответ на: комментарий от forCe

Зачем реализовывать всякую элементарщину каждый раз заново?

Затем, что ты просто несёшь херню ради херни. Если бы ты хоть чутка пытался думать - ты бы такую муть не нёс.

В разных задачах разная елементарщина, а если даже она одинаковая, кто тебе мешает её спастить?

Можешь показать на примере двух разных открытых проектов и объяснить, чем так радикально отличаются их связные списки/деревья/хэш-таблицы друг от друга и в чем там специфика проекта?

Я тебе ничего не собираюсь искать/объяснять.

Я тебе сказал как мы действуем - ты придумываешь задачу и мы пишем. Я пишу ванюз решение, а ты универсальное. И в тот моент, когда твоя жопа треснет, то авось ты что-то начнёшь понимать в этом мире, а не нести херню.

Я имел в виду набор структур данных и алгоритмов.

Откуда ты вылез, вася? Это никому нахрен не упало.

Он же там примитивен, но довольно удобен в использовании.

Кто?

Опять же, можешь привести пример открытых проектов, где реализация этих тривиальных плюшек быстрее STL'ной?

Если ты не понимаешь элементарных вещей, то я не обязан тебе что-то там искать. Я тебе уже сказал по какому условию я действую. Ты можешь придумать задачу и мы посоревнуемся.

И то, ты даже об stl знаешь в районе нуля. Все «быстрые» реализации в stl - это частные специализации. Такие балаболы реально думают, что у них конкатенирует строки std::basic_string::append(), а не std::string::append().

Мне в сишке нужна строка. В сишке я реализуют десяток функций и юзаю, а в stl я реализую тот же десяток функций на сишке, но за каким-то хером запихивают их в сотню бесполезных шаблонных абстракций.

Зачем мне это может понадобиться?

Чтобы сэкономить время на написании, тестировании, отладки давно известных тривиальных вещей.

Понимаешь, твой мир - это набор мифов и легенд, которые ты услышал за партой. За которыми ничего не стоит. Т.е. это иллюзорный мир, который к реальному миру не имеет никакого отношения.

И на чем же у меня сэкономится время?

Надёжность определяется простотой реализации. Зачем мне вместо простой, топорной и быстрой реализации того, что мне нужно - ваять какую-то неведомую универсальную, тормазную и дырявую херню, надёжность которой в районе нуля? Ваять которую в 100раз дольше.

Лишь по той причине, что мне какой-то студент толкает какие-то мифцы? Мне насрать, собственно как и пацанам.

TsarC ()
Ответ на: комментарий от svobodka_fighter

Такой свободы не существует

Почему же? Такие лицензии как Apache, MIT, BSD не требует открывать код.

amazpyel ★★★ ()
Последнее исправление: amazpyel (всего исправлений: 1)
Ответ на: комментарий от amazpyel

Спасибо, я понимаю идеологию. И не имею ничего против.

К чему твоё нытьё. Т.е. ты просто так вякнул про какую-то свободу и тут же сел в лужу?

Я ничего не требую.

Требуешь. Ты требуешь «свободы» от условий использования кода, который ты юзаешь.

Для этого есть другие лицензии.

Вот под другими лицензиями и юзай код. К чему кукаретинг про гпл?

Ну да, так и делают.

Делай. Зачем ты начал нести херню про «отобранную свободу»?

TsarC ()
Ответ на: комментарий от amazpyel

и да, можешь мне показать софт, который под лицензией GPL и который продается?

Зачем ему продаваться? К чему ты вообще высрал?

TsarC ()
Ответ на: комментарий от TsarC

Зачем ему продаваться?

Чтобы на хлеб заработать, очевидно.

К чему ты вообще высрал?

Лицензия ГПЛ позволяет брать плату за копию исходного кода программного продукта.

amazpyel ★★★ ()
Ответ на: комментарий от amazpyel

Ну всем насрать, объективных причин у тебя нет, ибо ты обделался как 5-летка. Это лишь твоя жалкая блажь, а блажь за которую ты не можешь как-то объективно агитировать - не стоит упоминания на публику. Это пустобрехство. Такой толкают на тематических сходках.

TsarC ()
Ответ на: комментарий от TsarC

Это моё право, чтобы мои труды юзали так, как я захочу. С чего ты требуешь от пацанов, чтобы они тебе давали свой код? Не хочешь таких условий - не юзай гпл-код. Пиши свой - плати бабки.

Ну чисто проприетарщик. Уймись, убогий, не позорь контору.

anonymous ()
Ответ на: комментарий от amazpyel

Чтобы на хлеб заработать, очевидно.

Что очевидно. Ты же покажешь предпосылки из контекста, которые позволили тебе свичнуться на еду?

Лицензия ГПЛ позволяет брать плату за копию исходного кода программного продукта.

И? К чему ты это толкаешь?

TsarC ()
Ответ на: комментарий от TsarC

Затем, что ты просто несёшь херню ради херни.

Узнаешь себя? Несколькими темами ранее ты даже простой программы не смог осилить

niemand ()
Ответ на: комментарий от Harald

вот mplayer в макоси
макоси

У бздунов все работает — вангую кривые руки или допотопную версию шланга.

anonymous ()
Ответ на: комментарий от Harald

Это не доказывает твое утверждение и не опровергает мое.

Reset ★★★★★ ()
Ответ на: комментарий от anonymous

Ну и ещё 32-битные бинарники уже никто не собирает. mplayer, кстати, в brew имеется, так что как-то его там собрали всё-таки.

rupert ★★★★ ()
Ответ на: комментарий от rupert

32-битные бинарники уже никто не собирает

да шо ты говоришь! уже появились 64-битные армы?

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

Ты что-то специально делаешь, чтобы пропускать новости? Надо очень постараться, чтобы пропустить СТОЛЬКО упоминаний о 64-битных ARM'ах.

i-rinat ★★★★★ ()
Ответ на: комментарий от Eddy_Em

А у моей бабушки вообще армов нет, поэтому их не существует.

HeipaVai1o ()

такой библиотеки просто нет

я в курсе существования glibc, queue.h и tree.h, коллекций в glib и пр.

division by zero

emulek ()
Ответ на: комментарий от amazpyel

можешь мне показать софт, который под лицензией GPL и который продается?

такого ПО полно, только ты неправильно понимаешь «продаётся». Конечно нет СПО, которое «продаётся школьникам-засранцам».

emulek ()
Ответ на: комментарий от forCe

можешь привести пример открытых проектов, где реализация этих тривиальных плюшек быстрее STL'ной?

а зачем «быстрее»? Например в моём проекте нужно:

1. создать несколько _имён_ файлов/каталогов, что-бы эти файлы открыть/прочитать.

2. распарсить простой конфиг и параметры КС.

3. выдавать сообщения об ошибках.

Все эти действия НЕ требуют скорости, и даже если будут выполняться мгновенно, программу это никак не ускорит.

Теперь скажи мне: зачем мне нужно STL? Учитывая, что мне для своих целей нужны «строки», с функционалом, которого в STL нет, и никогда не будет. Почему-бы их(свои классы) и не использовать для вышеозначенных целей?

emulek ()
Ответ на: комментарий от amazpyel

Лицензия ГПЛ позволяет брать плату за копию исходного кода программного продукта.

софт под GPL обычно под заказ пишут. Да, за деньги. Тебе, школьник, такой софт тупо не нужен. Тебе нужно готовое решение по типу Windows. Ну или андроид. Кстати, как думаешь, программисты писавшие андроид з/п получали?

emulek ()
Ответ на: комментарий от Reset

Решения на макросах (tree.h, queue.h) ok про производительности. Сравнимо с stl. Решения в стиле glib на void * и указателях на функции тормозят, да.

А давайте измерим, а?

// tst.cc
// g++ -std=c++11 -O3 `pkg-config --cflags --libs glib-2.0` tst.cc

#include <iostream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <chrono>
#include <stdlib.h>
#include <thread>
#include <glib.h>

const int cnt = 10 * 1000 * 1000;

static void measure(const std::string &title, std::function<void()> f) {
    auto start = std::chrono::steady_clock::now();
    f();
    auto end = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << std::setw(30) << title;
    std::cout << std::setw(7) << duration.count();
    std::cout << " ms" << std::endl;
}

int main(void) {
    measure("std::unordered_map",
        []() {
            std::unordered_map<int, int> h;
            srand(42);
            for (int k = 0; k < cnt; k ++)
                h[rand()] = 1;
            
            int lowcnt = 0;
            for (int k = 0; k < cnt; k ++)
                lowcnt += (h.find(k) != h.end());
            std::cout << h.size() << " " << lowcnt;
        }
    );

    measure("std::map",
        []() {
            std::map<int, int> h;
            srand(42);
            for (int k = 0; k < cnt; k ++)
                h[rand()] = 1;
        
            int lowcnt = 0;
            for (int k = 0; k < cnt; k ++)
                lowcnt += (h.find(k) != h.end());
            std::cout << h.size() << " " << lowcnt;
        }
    );

    measure("GHashTable",
        []() {
            GHashTable *h = g_hash_table_new(g_direct_hash, g_direct_equal);
            srand(42);
            for (int k = 0; k < cnt; k ++)
                g_hash_table_insert(h, GINT_TO_POINTER(rand()), GINT_TO_POINTER(1));

            int lowcnt = 0;
            for (int k = 0; k < cnt; k ++)
                lowcnt += !!g_hash_table_lookup_extended(h, GINT_TO_POINTER(k), NULL, NULL);
            std::cout << g_hash_table_size(h) << " " << lowcnt;
            g_hash_table_unref(h);
        }
    );

    return 0;
}
9976937 46549            std::unordered_map   7358 ms
9976937 46549                      std::map  15844 ms
9976937 46549                    GHashTable   4859 ms
i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

Где GTree? Где сравнение на чем-нибудь приближенном к реальности типа map<string, complex-struct-type> ?

Reset ★★★★★ ()
Ответ на: комментарий от i-rinat

Приличное сравнение вынесло бы генерацию случайных чисел и печать из функций, скорость которых сравнивается.

tailgunner ★★★★★ ()
Последнее исправление: tailgunner (всего исправлений: 2)
Ответ на: комментарий от i-rinat

А давайте измерим, а?

Поставил glib первым, добавил:

h.max_load_factor( .11 );
h.reserve( cnt ); 

И код на unordered_map стал быстрее, при том, что это не самая быстрая реализация для плюсов, а просто стандартная, коей в С нет.

anonymous ()
Ответ на: комментарий от Reset

Где сравнение на чем-нибудь приближенном к реальности

О как. А если бы числа подтвердили твою правоту, ты бы этот аргумент привёл? Несколько дней назад уже сравнивал с struct { int a, b, c, d; } в качестве ключа (значением был int), с похожим соотношением. В процессе твиканья получилось улучшить скорость варианта с unordered_map, если сразу выделить ему память под все элементы. На GCC 4.7. На GCC 4.9 какой-то регресс в скорости, и там всё равно вариант с GLib был быстрее.

Хочешь что-то доказать — пиши тесты сам. Мне достаточно того, что вариант с GLib не медленнее.

Где GTree?

9976937 46549            std::unordered_map   7223 ms
9976937 46549                      std::map  14758 ms
9976937 46549                    GHashTable   4759 ms
9976937 46549                         GTree  14481 ms
i-rinat ★★★★★ ()
Ответ на: комментарий от anonymous

И код на unordered_map стал быстрее

Отлично, спасибо.

i-rinat ★★★★★ ()
Ответ на: комментарий от rupert

http://pkg.freebsd.org/freebsd:10:x86:32/quarterly/All/mplayer2-2.0.20130428_...
Хотя могли и гцц собрать. С другой стороны, в build-dependencies его нет:
http://www.freshports.org/multimedia/mplayer/
http://www.freshports.org/multimedia/mplayer2/ зато есть фиксы типа

Fix build on i386 with clang.

Some inline asm requires 7 registers but only 6 are available because clang assumes the stack is 4-byte aligned and there's a local variable that requires 16-byte alignment so the stack has to be realigned which requires one register to be used as frame pointer.

anonymous ()
Ответ на: комментарий от i-rinat

Несколько дней назад уже сравнивал с struct { int a, b, c, d; } в качестве ключа (значением был int), с похожим соотношением.

Где код?

Reset ★★★★★ ()
Ответ на: комментарий от Reset

Заготовка теста есть, допиши к struct'у сравнивалки и проверь. Мне нет смысла ни доказывать тебе что-то, ни обманывать. Я и сам долгое время был уверен, что подход GLib тормозит, пока не решился проверить сам.

i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

Сравнение специально заточено под glib :) Хотя да, то, что он тут быстрее немного странно. Должно быть примерно равно.

Сравнивай нормальные реальные структуры с нормальными данными и нормальными ключами.

anonymous ()
Ответ на: комментарий от anonymous

Может, и заточено. Я большую часть времени пишу на C и пользуюсь GLib, так что всё может быть. Но я старался просто написать код так, как писал бы его для реальной задачи. Без специфических твиков.

Опиши, какие структуры и ключи являются нормальными, и какую последовательность операций тестировать. Покопаюсь как-нибудь. Мне самому интересны результаты.

i-rinat ★★★★★ ()
Ответ на: комментарий от zaz

Причина одна - на Си пишут только в двух случаях - Just for fun, или когда нужен очень быстрый и достаточно низкоуровневый код, но ассемблер не подходит. Для всего остального есть C++, C#, Pascal, python, PHP, BASIC, bash и т.д. Подход Just for fun обычно не приводит к созданию монструозных и в то же время быстрых библиотек с кучей документации, которые годятся, как аналог STL. Второй же случай требует оптимизации во всём, где это возможно, а оптимизацией в частном случае можно получить больше, чем в общем.

peregrine ★★★★★ ()
Ответ на: комментарий от Eddy_Em

Сейчас clang не так плох, как ты думаешь. Попробуй, может понравится.

peregrine ★★★★★ ()
Ответ на: комментарий от Harald

Половину из этой половины он не компилирует, так как там ошибки в коде, которые gcc спокойно ест.

peregrine ★★★★★ ()
Ответ на: комментарий от emulek

Возьми строки из Qt или gtk (можно через обертку gtkmm)

peregrine ★★★★★ ()
Ответ на: комментарий от TsarC

Затем, что ты просто несёшь херню ради херни. Если бы ты хоть чутка пытался думать - ты бы такую муть не нёс.

В разных задачах разная елементарщина

Я ничего не имею против специфичных плюшек. Но тема о том, что люди из проекта в проект пишут одну и ту же элементарщину. По крайней мере каких-то специфичных заточек не видно.

forCe ()
Ответ на: комментарий от TsarC

Я тебе сказал как мы действуем - ты придумываешь задачу и мы пишем. Я пишу ванюз решение, а ты универсальное. И в тот моент, когда твоя жопа треснет, то авось ты что-то начнёшь понимать в этом мире, а не нести херню.

Ты не понял. Тема не о том, почему ты или еще кто-то в какой-то конкретной задаче не стал использовать стандартные решения, а сделал свое решение, заточенное под задачу и т.д. и т.п. А о том, почему фактически одни и те же вещи в проектах на Си велосипедят с завидным упорством. Тема не о специальных решениях.

forCe ()
Ответ на: комментарий от anonymous

Поставил glib первым, добавил:

h.max_load_factor( .11 );
h.reserve( cnt );

h.reserve(cnt/2), и STL уже быстрее.

tailgunner ★★★★★ ()
Ответ на: комментарий от TsarC

И на чем же у меня сэкономится время?

Я сказал на чем. Меньше кода, меньше тестов, меньше отладки.

Надёжность определяется простотой реализации. Зачем мне вместо простой, топорной и быстрой реализации того, что мне нужно - ваять какую-то неведомую универсальную, тормазную и дырявую херню, надёжность которой в районе нуля? Ваять которую в 100раз дольше.

Ты о чем сейчас? Когда ты используешь STL или еще что-то, ты это просто используешь, а не реализуешь.

forCe ()
Ответ на: комментарий от tailgunner

h.reserve(cnt/2), и STL уже быстрее.

Очевидно, что результат может отличаться в зависимости от компилятора, архитектуры и пр.

anonymous ()
Ответ на: комментарий от peregrine

Не вижу смысла привязываься к gtkmm только из-за строк.

emulek ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.