adontz wrote:
> _>С алгоритмической точки зрения std::vector (массив) и std::list > (список) очень разные вещи. И не в менеджере памяти дело. > _>Или ты под массивом и списком понимаешь что-то другое? > Да разные, но внешне вполне одинаковые.
Какая разница что внешне? Это алгоритмически разные конструкции!
> На самом деле я каждый день крою создателей STL матом, потому что vector > и list это УЖОС! Надо было list и linked_list! Сколько новичков прочтя в
А что ты тогда хочешь от list? В чём разница от linked_list?
> условии про список элементов писали std::list хотя там больше подходит > std::vector. А сколько математиков пытались перемножить два std::vector?
Читайте доки, они рулез. Язык C++ не для новичков, и не заточен для математических расчётов.
> _>Но это сам язык не поддерживает, нельзя написать a[i,j,k], сравни с > тем же паскалем. Поэтому и не делали встроенной > _>поддержки, т.к. легко можно сделать при необходимости. > > Ну ведь можно a[i][j][k].
Ну так это не многомерный массив, а массив массивов массивов. Это алгоритмически разные конструкции.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, kan_izh, Вы писали:
_>Какая разница что внешне? Это алгоритмически разные конструкции!
Я говорю про упрощение реализации. А ты вообще я не понял про что.
_>А что ты тогда хочешь от list? В чём разница от linked_list?
Переименовать
vector -> list
list -> linked_list
_>Читайте доки, они рулез.
Давай пусть "+" вычитает, а "-" складывает. А всем кому не нравится будем отвечать — читайте доки. Интуитивную понятность ещё никто не отменял.
>> Ну ведь можно a[i][j][k]. _>Ну так это не многомерный массив, а массив массивов массивов.
adontz wrote:
> Я говорю про упрощение *реализации*. А ты вообще я не понял про что. > > _>А что ты тогда хочешь от list? В чём разница от linked_list? > > Переименовать > vector -> list > list -> linked_list
То что вектор не список это точно, более бы подошло array, но название vector намекает на одномерность. Ибо 2-d array
соответсвует матрице. А вот 2-d векторов не бывает.
> _>Читайте доки, они рулез. > > Давай пусть "+" вычитает, а "-" складывает. А всем кому не нравится > будем отвечать — читайте доки. Интуитивную понятность ещё никто не отменял.
Не знаю, для меня вектор всегда был одномерным массивом. Для меня интуитивно понятно.
То что они не умножаются — ну и правильно, ибо они потенциально могут быть разной длины. Да и умножать вектора можно по
разному — скалярно, векторно, смешанно.
>> > Ну ведь можно a[i][j][k]. > _>Ну так это не многомерный массив, а массив массивов массивов. > Это смотря как написать.
А как можно написать? Понятно, что можно положить в непрерывнй участок памяти, но это будет не то же самое, что
a[i + M*j + M*N*k], нужна доп память под указатели.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, kan_izh, Вы писали:
>> vector -> list >> list -> linked_list _>То что вектор не список это точно,
Вектор это не связанный список. Ещё бывает двусвязный. А просто список это упорядоченный набор и не более того. По-английски пишут list of values, а не vector of values.
_>более бы подошло array,
Это уже не просто упорядоченный, но и непрерывно расположенный в памяти. Кстати я очень не люблю хвалить .Net Framework, но там весьма толковые названия контейнеров.
_>но название vector намекает на одномерность. Ибо 2-d array соответсвует матрице. А вот 2-d векторов не бывает.
Вот-вот. У тебя не таблица, а именно матрица. А потом ещё говоришь что не хочется перемножать вектора.
>> Это смотря как написать. _>А как можно написать? Понятно, что можно положить в непрерывнй участок памяти, но это будет не то же самое, что _>a[i + M*j + M*N*k], нужна доп память под указатели.
adontz wrote:
>> > vector -> list >> > list -> linked_list > _>То что вектор не список это точно, > > Вектор это не связанный список. Ещё бывает двусвязный. А просто список > это упорядоченный набор и не более того. По-английски пишут list of > values, а не vector of values.
Потому что понятие "список" обычно не содержит понятие "индекс". Поэтому список аргументов функции — действительно
список. А вот вектор имеет индекс, а это далеко не во всех списках надо.
> _>более бы подошло array, > Это уже не просто упорядоченный, но и непрерывно расположенный в памяти. > Кстати я очень не люблю хвалить .Net Framework, но там весьма толковые > названия контейнеров.
array бывает многомерный, vector всегда одномерный. Это в точности соответсвует поведению std::vector.
> _>но название vector намекает на одномерность. Ибо 2-d array > соответсвует матрице. А вот 2-d векторов не бывает. > Вот-вот. У тебя не таблица, а именно матрица. А потом ещё говоришь что > не хочется перемножать вектора.
?
Термины "таблица" и "матрица" — синонимы. Вообще говоря не совсем, в математике таблицы бывают бесконечны, у матриц
всега строго заданы размеры, но для компьютеров бесконечность значение не имеет.
>> > Это смотря как написать. > _>А как можно написать? Понятно, что можно положить в непрерывнй участок > памяти, но это будет не то же самое, что > _>a[i + M*j + M*N*k], нужна доп память под указатели. > В смысле смотря как написать operator[].
Я имел в виду поддержку языка, встроенные типы. Многомерные массивы встроены в паскаль, в С нет.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Pavel Dvorkin,
PD>Насколько я понимаю, это все же класс System.Array. В хипе он, а не в стеке. А хотелось бы все же в стеке. Да и без unsafe тоже бы не помешало.
Можно спросить: А зачем хранить массивы в стеке? Если учесть, что выделение и освобождение массива в куче может быть быстрее?
adontz wrote: > _>То что вектор не список это точно, > Вектор это не связанный список. Ещё бывает двусвязный. А просто список > это упорядоченный набор и не более того. По-английски пишут list of > values, а не vector of values.
Вектор и список — это алгоритмически совершенно разные структуры. В
частности, для вектора всегда определена операция взятия элемента по
индексу. Для списка такой операции может не быть (для кольцевого списка,
например).
Соответственно, у списка и вектора разные характеристики по
алгоритмической сложности операций.
> Это уже не просто упорядоченный, но и непрерывно расположенный в памяти. > Кстати я очень не люблю хвалить .Net Framework, но там весьма толковые > названия контейнеров.
Вообще-то, std::vector гарантировано непрерывно расположен в памяти.
V>Определение границ — из рук вон плохо. Но я, например, не припоминаю, когда и зачем мне такая фича была нужна. К тому же, что есть граница у многомерного массива?
Тривиально, батенька. Храним массив с парами чисел — границами по каждой размерности. При занесении элемента в массив обновляем эти числа при необходимости Очень дешевая операция по сравнению с занесением в хэш.
V>Добавление в хвост — тоже плохо, т.к. нужно знать верхнюю границу. Но эту проблему можно обходить разными способами в зависимости от контекста.
См. выше. Имея границы — проблем нет.
V>Единственный минус этого подхода: hash — это более тормозная штука, нежели непрерывный массив в памяти. Но, господа, программы тормозят не из-за скорости базовых операций, а из-за неоптимальности алгоритмов, и по этой причине разгрузка головы программера от борьбы с границами массивов может привести к тому, что в результате программа будет работать быстрее!
Хэш, к сожалению, очень тормозная штука. И для плюсового киллера я бы не рекомендовал его...
V>>Взять значение по индексу — идеально.
AVK>Это классическая то хеш-таблица? Ничего не путаешь?
С массивом как непрерывной областью памяти не сравнить, но в остальном достаточно быстро.
V>>Перебор значений — даже лучше, чем в классике (если в синтаксис добавить оператор ForEach), т.к., во-первых, в разреженном массиве не нужно анализировать пустоты, а во-вторых, оператор ForEach может служить синтаксической основой параллелизма. Единственная проблема — ForEach должен возвращать пару (индекс, значение).
AVK>А как быть с сохранением порядка?
А это, наверное, надо делать отдельную конструкцию, в которой хранить используемые индексы
V>>Определение границ — из рук вон плохо. Но я, например, не припоминаю, когда и зачем мне такая фича была нужна. К тому же, что есть граница у многомерного массива?
AVK>А что такое определение границ?
Они, наверное, для итерации по измерениям нужны?
V>>Удаление значения — без проблем, если не забивать голову сдвигом хвоста на освободившееся место.
AVK>А забивать не надо, если мы претендуем на универсальность. А еще вопрос качественного хеш-кода тоде не так прост. А еще в хеше нельзя хранить повторяющиеся ключи.
А в одном элементе массива можно хранить два значения?
Ну не совесем. Раз так в цать по производительности могут различаться.
V>Да уж, с этим проблема... ForEach — это действительно беспорядочная штука. Видимо, решение сдесь только одно — сделать упорядоченную выборку функцией такого "массива"
К слову говоря, ForEach не подразумевает сохранения порядка. Вам же просто нужно пройтись по всем элементам в подмножестве? Ну а то, что в большинстве языков он порядок выдерживает — это уже проблемы авторов. Вы подумайте, в какой части алгоритмоыв важен порядок? Сумму элементов считать — с любого можно начать. Максимум/минимум — тоже с любого...
Lazy Cjow Rhrr wrote:
> PD>Насколько я понимаю, это все же класс System.Array. В хипе он, а не в > стеке. А хотелось бы все же в стеке. Да и без unsafe тоже бы не помешало. > > Можно спросить: А зачем хранить массивы в стеке? Если учесть, что > выделение и освобождение массива в куче может быть быстрее?
Если массивы маленькие, например, 3-4 элемента и их много? Конечно можно завести 3-4 переменные — но это не всегда удобно.
int coords1[3];
double coords2[3];
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
kan_izh,
>> Можно спросить: А зачем хранить массивы в стеке? Если учесть, что >> выделение и освобождение массива в куче может быть быстрее? _>Если массивы маленькие, например, 3-4 элемента и их много? Конечно можно завести 3-4 переменные — но это не всегда удобно.
_>int coords1[3]; _>double coords2[3];
Я продолжу.
1. Мы обобщаем алгоритм на случай размерности как параметра:
int coords1[n];
double coords2[n];
Картина Репина "Приплыли".
2. У нас необобщаемый алгоритм на случай размерности равной 3. Поскольку ты предлагаешь для этой цели использовать массивы выделяемые в стеке, то компилятору известны все эти массивы. Он (компилятор) вставляет инструкции предписывающие коллектору выделить всю эту память пачкой. А прибираться можно с некоторой долей ленивости. Итого получаем:
а. Стек: инкремент указателя, декремент указателя;
б. Куча: инкремент указателя, ленивый декремент указателя;
Получается, что куча будет работать _не хуже_ стека. Ловкость рук и никакого мошенничества.
В существующем на данный момент дотнете компиляторы конечно такой магии не делают, поэтому там выделение-освобождение на стеке происходит быстрее, и разговоры про маленькие массивы на стеке вполне имеют смысл.
Но мы вроде как усиленно мечтаем о массивах в некоторой гипотетической среде, не так ли?
Lazy Cjow Rhrr wrote: > 1. Мы обобщаем алгоритм на случай размерности как параметра: > int coords1[n]; > double coords2[n]; > Картина Репина "Приплыли".
А какие проблемы? При n<некоторое_разумное_число — все будет нормально.
В C можно делать так:
void some_func(int n)
{
...
int f;
int arr[n];
for(f=0;f<n;f++)
arr[f]=f*f;
}
В Стандарте С++ пока такого нет, так что приходится делать так:
void some_func(int n)
{
int *arr=(int*)alloca(n*sizeof(int));
for(int f=0;f<n;f++)
arr[f]=f*f;
}
Вся память — в стеке.
> а. Стек: инкремент указателя, декремент указателя;
Причем на уровне процессора.
> б. Куча: инкремент указателя, ленивый декремент указателя;
Еще нужно: запись информации о блоке, для MT-аллокаторов могут
потребоваться блокировки/атомарные операции.
> Получается, что куча будет работать _не хуже_ стека. Ловкость рук и > никакого мошенничества.
Даже лучше алокаторы во много раз медленнее стека.
Lazy Cjow Rhrr wrote:
> _>int coords1[3]; > _>double coords2[3]; > > Я продолжу. > > 1. Мы обобщаем алгоритм на случай размерности как параметра: > > int coords1[n]; > double coords2[n]; > Картина Репина "Приплыли".
Далеко не всегда нужно. Пространство наше трёхмерное. А когда физики придумают n-мерную теорию реальности — тогда я не
погнушаюсь, перепишу код.
> 2. У нас необобщаемый алгоритм на случай размерности равной 3. Поскольку > ты предлагаешь для этой цели использовать массивы выделяемые в стеке, то > компилятору известны все эти массивы. Он (компилятор) вставляет > инструкции предписывающие коллектору выделить всю эту память пачкой. А > прибираться можно с некоторой долей ленивости. Итого получаем: > а. Стек: инкремент указателя, декремент указателя;
Стек: 0 операций! Вообще нулевая стоимость!
Ибо изменится лишь константа, смещающая указатель на стек при входе в функцию. Вместо 4 байт под указатель будет смещено
на 12 байт под 3 значения int.
Фактически
int coords1[3];
и
int coords1_1, coords1_2, coords1_3;
абсолютно эквивалентные конструкции в C. Только использование удобнее.
> б. Куча: инкремент указателя, ленивый декремент указателя; > Получается, что куча будет работать _не хуже_ стека. Ловкость рук и > никакого мошенничества. > > В существующем на данный момент дотнете компиляторы конечно такой магии > не делают, поэтому там выделение-освобождение на стеке происходит > быстрее, и разговоры про маленькие массивы на стеке вполне имеют смысл.
одним словом
Если бы кабы, то во рту росли б грибы. (с) народ
> Но мы вроде как усиленно мечтаем о массивах в некоторой гипотетической > среде, не так ли?
Мечтать не вредно, вредно не мечтать. (с) не знаю кто
Просто эта гипотетическая среда, имхо, должна позволят оба варианта массивов, как в C.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Cyberax,
>> Получается, что куча будет работать _не хуже_ стека. Ловкость рук и >> никакого мошенничества.
C>Даже лучше алокаторы во много раз медленнее стека.
В каких случаях?
Эти аллокаторы делались с целью максимизации скорости в каком среднем сценарии использования. Возьмёмся максимизировать скорость в некотором частном случае и вуаля. Я ведь давал ссылку на статью, там вот как раз такой результат (хотя практически этот результат использовать не получится, потому что тогда будет хромать как раз вот тот средний случай).
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
