C++: массив элементов переменного размера

Vector. Если даже ты заранее не знаешь, сколько будет элементов, и будешь просто закидывать их по одному, то в среднем каждый элемент переживёт только одно перемещение независимо от общего числа.

Файлов может быть несколько сотен тысяч или больше

Я так думаю, что ты упрешься в производительность ФС раньше, чем в std::vector.

он будет иногда перестраиваться

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

Вообще ты по-моему пытаешься экономить на спичках.

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

Если уж руками реализовывать, то используй string* + realloc + placement new. Эффективнее некуда.

string*

Тут имеется ввиду буфер под строки вместо вектора, а не то, что каждая строка будет на куче.

Для полной оптимизации еще строки можно заменить на свою стуктурку из указателя и размера. У нее sizeof должен быть меньше чем у std::string.

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

Очевидно, связанный список не нужен. В зависимости от размера объекта нужно сразу добавлять в vector или в вектор из uniqe_ptr, вектор можно заменить на deque.

.. массив сортировать и всячески мудрить.

Единственный способ существенно ограничить потребление памяти это мудрить сразу в процессе обхода и ничего не сортировать. В общем, любые оптимизации тут зависят от последующей обработки данных - сначала нужно сделать как-то работающий прототип и потом смотреть что в нём не так с точки зрения потребления ресурсов. Может быть твоё мудрение само по себе настолько тормозное, что нет смысла что-то особенное делать со стадией подгузки данных.

... в среднем каждый элемент переживёт только одно перемещение независимо от общего числа.

нет, не одно.

std::multimap ?

http://pastebin.com/MQRWT5Py

Скорее log2(N) перемещений. Но ты можешь сделать vec.reserve(100000) сразу после создания.

или в вектор из uniqe_ptr

Нахрена? Строка это и так обычно несколько указателей (begin/end/capacity). Данные копироваться не будут, в том числе при сортировке. А unique_ptr это еще одно косвенное обращение памяти и еще пара new/delete.

нет, не одно.

Окей, меньше двух даже для самых неудачных размеров. Вообще, зависит от реализации, конечно. Но если где-то больше или вообще растёт с увеличением числа элементов, то такой STL надо срочно выкинуть.

Хочется, чтобы это не занимало десятки секунд

А сколько оно занимает в самой простой реализации? Ты не под калькулятор, поди, пишешь.
Есть же закон: сначала напиши чтоб работало, потом оптимизруй.

Насколько я понимаю, std::vector в принципе подходит, но при добавлении элементов он будет иногда перестраиваться

std::vector, перестраиваясь, каждый раз выделяет памяти в 2 раза больше, чем было. Итого, для 100 000 элементов он у тебя перестроится максимум 17 раз. Не думаю что это много. Но, если тебя и это не устраивает, всегда есть reserve.

и доступ к элементу в итоге будет не быстрее.

Этого не понял. Поправьте если я не прав, но std::vector самый быстрый с точки зрения рандомного доступа к элементу.

Нахрена? Строка это и так обычно несколько указателей (begin/end/capacity). Данные копироваться не будут, в том числе при сортировке. А unique_ptr это еще одно косвенное обращение памяти и еще пара new/delete.

Если прекратишь одновременно обдалбываться и писать на форум, то неожиданно для себя найдёшь ответ и на этот вопрос.

Если прекратишь одновременно обдалбываться и писать на форум, то неожиданно для себя найдёшь ответ и на этот вопрос.

Так прекращай, это у тебя поток сознания про нечто отвлеченное от задачи ТС пошел.

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

Опять не угадал. В среднем будет константное кол-во перемещений, заранее не определённое для std::vector.

ВОт вам эталонный код:

#include <algorithm>
#include <dirent.h>
#include <string>
#include <vector>
using namespace std;

int main()
{
    DIR* d = opendir( "/usr/bin" );
    if( !d )
        return 1;

    vector<string> names;
    
    for( dirent* e ; e = readdir( d ) ; )
    {
        for( int i = 0 ; i < 1000 ; ++i )
            names.emplace_back( e->d_name );
    }
    
    closedir( d );
    
    sort( names.begin(), names.end() );
}

Кто сможет ускорить его в два раза?

Опять не угадал.

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

Это ты небось считаешь, что после перемещения это будет уже новый элемент, поэтому не более одного?

сразу добавлять в vector или в вектор из uniqe_ptr, вектор можно заменить на deque

Если я правильно читаю маны, в этих классах элемент имеет фиксированный размер. Придётся сразу выделять 4K на имя файла, либо вектор будет перестраиваться при сохранении более длинного имени файла.

мудрить сразу в процессе обхода

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

нужно сделать как-то работающий прототип

Дык есть уже. Иногда на десятках тысяч файлов десятки секунд крутится.

Кто сможет ускорить его в два раза?

Ну ладно, вот вам вариант в два раза быстрее. Кто сможет еще ускорить?

#include <cstring>
#include <dirent.h>
#include <memory>
#include <set>
using namespace std;

struct tstring 
{
    tstring( char* s ) 
    {
        l_ = strlen( s );
        s_ = (char*) malloc( l_ + 1 );
        
        memcpy( s_, s, l_ + 1 );
    }
    
    tstring( tstring&& s ) = delete;
    tstring( const tstring& s ) = delete;
    ~tstring( void ) { free( s_ ); }
    
    void operator=( tstring&& s ) = delete;
    void operator=( const tstring& s ) = delete;
    bool operator<( const tstring& s ) const { return strcmp( s_, s.s_ ) < 0; }
    
    char*  s_;
    size_t l_;
};

int main()
{
    DIR* d = opendir( "/usr/bin" );
    if( !d )
        return 1;

    set<tstring> names;
    
    for( dirent* e ; e = readdir( d ) ; )
    {
        for( int i = 0 ; i < 1000 ; ++i )
            names.emplace( e->d_name );
    }
    
    closedir( d );
}

Kroz

сколько оно занимает в самой простой реализации?

До примерно одной секунды на тысячу файлов.

Kroz

Xenesz

и доступ к элементу в итоге будет не быстрее.

Этого не понял.

Я повнимательнее почитал про вектор, ко времени доступа претензий больше не имею.

Это ты небось считаешь, что после перемещения это будет уже новый элемент, поэтому не более одного?

Нет, конечно же, так было бы совсем неинтересно :) Первые элементы будут перемещены большее число раз, последние — вообще не будут перемещаться. Для классической стратегии выделения памяти по степеням двойки получается ограничение сверху в два перемещения (про одно я погорячился, это нижняя граница) для каждого элемента в среднем. Для других стратегий результат может отличаться, но будет там 2 или 1.5, обычно уже не так важно. Особенно если это именно перемещение, а не старое-доброе копирование.

Дык есть уже. Иногда на десятках тысяч файлов десятки секунд крутится.

Либо твоя реализация очень кривая, либо узкое место вообще не в твоем коде.

Если я правильно читаю маны, в этих классах элемент имеет фиксированный размер.

Ну да, как-то так.

Придётся сразу выделять 4K на имя файла, либо вектор будет перестраиваться при сохранении более длинного имени файла.

std::string имеет фиксированный размер, обычно он состоит из указателя на другой кусок памяти переменного размера. Никаких 4к на имя выделять не нужно.

Дык есть уже. Иногда на десятках тысяч файлов десятки секунд крутится.

Нужно же посмотреть почему так долго, для описанной в топике работы это слишком много если брать средненький x86 последнего десятка лет (должны быть секунды на 1М). Ты же наверняка ещё делаешь stat на каждый файл, так что весь процесс может сильно тормозить если работаешь с hdd и с непрогретым inode кешом. С помощью strace -c и perf top можно попробовать посмотреть во что именно всё упирается.

... по степеням двойки получается ограничение сверху в два перемещения (про одно я погорячился, это нижняя граница) для каждого элемента в среднем.

Всё было правильно. Для удвоения в среднем будет не более 1го перемещения, около двойки будет для роста примерно в 1.5 раза.

А что, сразу узнать сколько файлов в каталоге религия не позволяет?

При работе со списком основные накладные расходы это выделение памяти под элемент. Если Вы все равно память под каждый новый элемент выделяете, то почти без разницы (ну или разница не больше чем вдвое).

Скорее всего Вы занимаетесь преждевременной оптимизацией, сделайте сначала со списком и посмотрите на что уходит время работы.

Спасибо, таки почитал про реализацию std::string.

узнать сколько файлов в каталоге

Строки с путями-именами файлов приходят с stdin. Это могут быть не все реально находящиеся в каталоге файлы, а часть.

прочитать имена файлов из каталога, отсортировать по размеру

если вдруг интересно мой говнокод моя реализация на C

Имена файлов я читаю с stdin. Иногда нужны не все файлы, и я не хочу велосипедить gnu find.

Имена файлов я читаю с stdin.

так твоя задача тогда вообще изи

хотя я не знаю зачем тебе это нужно писать на C/C++, если запросто можно взять какой-нибудь perl и быть счастливым

Perl в принципе хорош, но он чуть медленнее, и как там оптимальнее всю эту беду хранить, я не знаю и наверное не должен знать. На сях или крестах я примерно представляю, как память выделяется и всё такое.

если ты получаешь список файлов в stdin, а не в самой программе, то один фиг на чем писать, медленне вряд-ли будет, а оверхед по затратам памяти ты и так себе сделал

и как там оптимальнее всю эту беду хранить

а как нравится так и храни. Хочешь - в хешах (это они так называют ассоциативные массивы), а хочешь - в массивах. Я бы брал в массивах. Сортировка там вообще раз плюнуть

Списки - это плохо, так как они приводят к промахам в кэше процессора.

my %stats;
while(<>) {
  -f $_ && $stats{$_} = -s $_;
}

print "$_\n" for (sort {$stats{$a} > $stats{$b};} keys %stats);

Как-то так, не проверял и на перле давно не писал.

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

Синтаксис условия починил

-f $_ && { $stats{$_} = -s $_ };

sort {$stats{$a} > $stats{$b};} keys %stats

sort {$stats{$a} > $stats{$b};} keys %stats

но ни разу не бывает истинной (выхлоп скрипта ноль строк).

Это сортировка ключей по значениям (values).

выхлоп скрипта ноль строк

Это из-за доаольно известного pitfall'a c чтением STDIN, надо явно: <STDIN>:

my %stats;
while(<STDIN>) {
  chomp;
  $stats{$_} = -s $_ if (-f $_);
}

print "$_\n" for (sort {$stats{$a} > $stats{$b}} keys %stats);

... и конкурс на однострочник обьявляется открытым!

my %stats = map { $_ => -s $_ } grep { -f } map { chomp; $_ } <STDIN>;
print "$_\n" for (sort {$stats{$a} > $stats{$b}} keys %stats);

Вот мы с тобой взяли и внаглую скатили тему =)

Выхлоп есть, но делается ли сортировка, и по какому критерию, неясно. Не по размеру файла, это точно.

Да ладно, тема не бог весть какая.

Не по размеру файла, это точно.

упс, лови

my %stats = map { $_ => -s $_ } grep { -f } map { chomp; $_ } <STDIN>;
print "$_\n" for (sort {$stats{$a} <=> $stats{$b}} keys %stats);

в этих классах элемент имеет фиксированный размер. Придётся сразу выделять 4K на имя файла

вы в курсе, что std::string имеет фиксированный размер? это, на самом деле, указатель на массив char, в котором первых n байт — размер данных, остальные байты — сами данные. причём, указатель указывает на начало данных, а не на начало массива.

скоростью доступа к элементу. ну и вектор можно поместить целиком или частично в кеш, а список — нет.

ну и лист память ест дополнительно на размер указателя. для хранения строк это может оказаться заметно. 8 байт весит указатель == примерно 8 символов на каждую строку.

Спасибочки, работает.

Да, я уже почитал про размещение std::string и про std::vector<std::string> на всякий случай.