LINUX.ORG.RU

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

 


0

3

Добрейшего всем.

Нужно прочитать пути-имена файлов с stdin, отсортировать по размеру и посчитать кое-какую статистику. Файлов может быть несколько сотен тысяч или больше. Хочется, чтобы это не занимало десятки секунд и не съедало много памяти.

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

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

Какие ещё варианты?

UPD Исправлено: s/имена файлов из каталога/пути-имена файлов с stdin/

★★★★

Последнее исправление: Xenesz (всего исправлений: 1)

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

const86 ★★★★★
()

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

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

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

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

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

no-such-file ★★★★★
()
Последнее исправление: no-such-file (всего исправлений: 1)

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

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

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

string*

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

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

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

anonymous
()

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

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

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

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

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

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

нет, не одно.

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

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

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

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

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

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

нет, не одно.

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

const86 ★★★★★
()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

mashina ★★★★★
()

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

#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() );
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#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 );
}
anonymous
()
Ответ на: комментарий от Kroz

Kroz

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

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

Kroz

Xenesz

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

mashina ★★★★★
()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

reprimand ★★★★★
()
Последнее исправление: reprimand (всего исправлений: 1)

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

Deleted
()
Ответ на: комментарий от Xenesz
my %stats;
while(<>) {
  -f $_ && $stats{$_} = -s $_;
}

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

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

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

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

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

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

-f $_ && { $stats{$_} = -s $_ };
но
sort {$stats{$a} > $stats{$b};} keys %stats
— не помню, что это за конструкция и не понимаю, почему она работает, но ни разу не бывает истинной (выхлоп скрипта ноль строк).

Xenesz ★★★★
() автор топика
Ответ на: комментарий от Xenesz
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);

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

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

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

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

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

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

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

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

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

упс, лови

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

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

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

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

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

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

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

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

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

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

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