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

поговори мне тут

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кто?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я говорил о том, чем мне не нравится гпл.

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

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

OsmAnd+.

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

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

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

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

Спасибо

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

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

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

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

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

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

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

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

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

Иди к мамке анскильный питах!

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

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

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

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

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

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

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

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

Он еще на utf-8 не перешел, какие там arm64, лол.

у меня все армы 32-битные!

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

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

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

division by zero

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

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

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

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

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

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

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

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

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

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

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

Решения на макросах (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

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

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

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

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

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

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

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

О как. А если бы числа подтвердили твою правоту, ты бы этот аргумент привёл? Несколько дней назад уже сравнивал с 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

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

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

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.

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

Где код?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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