Итак, предположим что Вы причастны к разработке нового императивного ЯП(возможно он позиционируется как "С++ killer" (Да, сильно, а что делать )). Какими на Ваш взгляд должны бы быть встроенные в язык массивы? (А может и не надо "встроенности"? (std::array))
Предпологается что язык статически типизирован(как Вы это понимаете) и имеет некоторый встроенный набор базовых типов. Кроме того, предположим, что ссылок и указателей на данном этапе нет(но они могут появиться, исходя из Ваших предположений и пожеланий).
Итак(да/нет/мысли):
1. Массив как встроееный тип.
2. Массив как агрегат (а'ля С++).
3. Непрерывное размещение элементов массива в памяти.
4. Совместимость с C++ (see 3)
5. Массивы N-го порядка как массив из массиво N-1 порядка.
6. Непрерывная область памяти + encode lambda expression.
7. Прямоугольные/jagged/sparse arrays
8. ?
9. синтаксис
10. и в некотором сысле семантика...
+
11. Вопросы оптимизации
12. возврат\передача by value (в т.ч. массивов с неизвестным размером)
13. splice's
14. способы итерации
15. любые мысли
Интересут все(на данном этапе ФЯ идут боком; да и массивы в ИЯ ортогональны), так как многие источники по language design умалчивают этот вопрос, либо довольствуются известными конструкцимя.
Проверка выхода за границы особо не интересут (ибо сделать ее не составляет труда).
Здравствуйте, Lande, Вы писали:
L>Вопрос к RSDN All:
L>Итак, предположим что Вы причастны к разработке нового императивного ЯП(возможно он позиционируется как "С++ killer" (Да, сильно, а что делать )). Какими на Ваш взгляд должны бы быть встроенные в язык массивы? (А может и не надо "встроенности"? (std::array))
Здравствуйте, Lande, Вы писали:
L>Здравствуйте, FR, Вы писали:
FR>>Предлагаю посмотреть на D и python.
L>Я уже столько всего пересмотрел..
L>+ L>
L>...либо довольствуются известными конструкцимя.
А ты что ищешь неизвестное или самое удобное?
Если второе то по моему в D это уже реализованно, если еще добавить туда несколько вкусных штук из питона 2.4 (отрицательные индексы, разворот массивов и т. п.) то будет близко к идеалу.
Здравствуйте, Lande, Вы писали:
L>Итак, предположим что Вы причастны к разработке нового императивного ЯП(возможно он позиционируется как "С++ killer" (Да, сильно, а что делать )). Какими на Ваш взгляд должны бы быть встроенные в язык массивы? (А может и не надо "встроенности"? (std::array))
matlab
L>Итак(да/нет/мысли):
L>1. Массив как встроееный тип.
да
L>2. Массив как агрегат (а'ля С++).
да
L>3. Непрерывное размещение элементов массива в памяти. L>4. Совместимость с C++ (see 3) L>5. Массивы N-го порядка как массив из массиво N-1 порядка. L>6. Непрерывная область памяти + encode lambda expression. L>7. Прямоугольные/jagged/sparse arrays
да. это накладывает ограничения на пункты 1-6
L>8. ? L>9. синтаксис L>10. и в некотором сысле семантика...
matlab
L>+ L>11. Вопросы оптимизации
да
L>12. возврат\передача by value (в т.ч. массивов с неизвестным размером)
Здравствуйте, Lande, Вы писали:
L>Вопрос к RSDN All:
L>Итак, предположим что Вы причастны к разработке нового императивного ЯП(возможно он позиционируется как "С++ killer" (Да, сильно, а что делать )). Какими на Ваш взгляд должны бы быть встроенные в язык массивы? (А может и не надо "встроенности"? (std::array))
А кроме синтаксических улучшений, что еще в языке предполагается?
Здравствуйте, Lande, Вы писали:
L>Вопрос к RSDN All:
L>Итак, предположим что Вы причастны к разработке нового императивного ЯП(возможно он позиционируется как "С++ killer" (Да, сильно, а что делать )). Какими на Ваш взгляд должны бы быть встроенные в язык массивы? (А может и не надо "встроенности"? (std::array))
Такое соображение: одномерный массив — это отображение (оно же мэппинг, оно же hash) числа на значение. Соответственно, двумерный массив — это отображение пары чисел (что такое пара чисел? а это ведь тоже массив!) на значение.
Посмотрим, хорошо ли hash держит типичные массивные операции:
Взять значение по индексу — идеально.
Положить значение — фантастически (т.е. мы даже за границы массива никогда не сможем выпрыгнуть).
Перебор значений — даже лучше, чем в классике (если в синтаксис добавить оператор ForEach), т.к., во-первых, в разреженном массиве не нужно анализировать пустоты, а во-вторых, оператор ForEach может служить синтаксической основой параллелизма. Единственная проблема — ForEach должен возвращать пару (индекс, значение).
Определение количества элементов — тут тоже всё ОК.
Определение границ — из рук вон плохо. Но я, например, не припоминаю, когда и зачем мне такая фича была нужна. К тому же, что есть граница у многомерного массива?
Добавление в хвост — тоже плохо, т.к. нужно знать верхнюю границу. Но эту проблему можно обходить разными способами в зависимости от контекста.
Удаление значения — без проблем, если не забивать голову сдвигом хвоста на освободившееся место.
Единственный минус этого подхода: hash — это более тормозная штука, нежели непрерывный массив в памяти. Но, господа, программы тормозят не из-за скорости базовых операций, а из-за неоптимальности алгоритмов, и по этой причине разгрузка головы программера от борьбы с границами массивов может привести к тому, что в результате программа будет работать быстрее!
Впрочем, ограниченные непрерывные массивы тоже можно оставить как подвид для работы, например, с битмэпами.
(да/нет/мысли): L>1. Массив как встроееный тип.
Да, хотя и не обязательно. L>2. Массив как агрегат (а'ля С++).
Да. L>3. Непрерывное размещение элементов массива в памяти.
Уже сказал. L>4. Совместимость с C++ (see 3)
Для ковыряния в памяти можно сделать какую-нибудь штуку типа BINARY. L>5. Массивы N-го порядка как массив из массиво N-1 порядка.
Это точно никуда не годится! В системах, где так сделано, массвами порядка больше 1 вообще нельзя пользоваться!
Кстати, hash снимает проблему многомерности легко и наиболее естественно.
Здравствуйте, Voblin, Вы писали:
V>Взять значение по индексу — идеально.
Это классическая то хеш-таблица? Ничего не путаешь?
V>Перебор значений — даже лучше, чем в классике (если в синтаксис добавить оператор ForEach), т.к., во-первых, в разреженном массиве не нужно анализировать пустоты, а во-вторых, оператор ForEach может служить синтаксической основой параллелизма. Единственная проблема — ForEach должен возвращать пару (индекс, значение).
А как быть с сохранением порядка?
V>Определение границ — из рук вон плохо. Но я, например, не припоминаю, когда и зачем мне такая фича была нужна. К тому же, что есть граница у многомерного массива?
А что такое определение границ?
V>Удаление значения — без проблем, если не забивать голову сдвигом хвоста на освободившееся место.
А забивать не надо, если мы претендуем на универсальность. А еще вопрос качественного хеш-кода тоде не так прост. А еще в хеше нельзя хранить повторяющиеся ключи.
... << RSDN@Home 1.2.0 alpha rev. 646 on Windows XP 5.1.2600.131072>>
Здравствуйте, Lande, Вы писали:
L>Итак, предположим что Вы причастны к разработке нового императивного ЯП(возможно он позиционируется как "С++ killer" (Да, сильно, а что делать )). Какими на Ваш взгляд должны бы быть встроенные в язык массивы? (А может и не надо "встроенности"? (std::array))
L>1. Массив как встроееный тип.
Пригодится.
L>2. Массив как агрегат (а'ля С++).
Я бы даже сказал — а-ля Си.
L>3. Непрерывное размещение элементов массива в памяти.
Пункты 2 и 3 пригодятся, если этот язык — действительно C++killer. То есть предполагает работу с низким уровнем (в том числе).
Может быть, желательно разнести POD-массивы (непрерывные, с агрегатной инициализацией) и высокоуровневые коллекции (абстрагированные от вопросов размещения).
Хотя агрегаты — сами по себе вещь приятная.
В С++ невозможно подставлять в выражения массивы-литералы (за исключением строк). А иногда хочется... вот и изобретают велосипеды по конструированию коллекций через бинарные операторы.
L>4. Совместимость с C++ (see 3)
Джентельменский минимум — совместимость с Си по POD-структурам и совместимость с COM по формату виртуальных вызовов.
Возможно, что COM-интерфейсы можно специальным образом помечать, чтобы компилятор знал: здесь — нужна совместимость, а в остальных случаях выбирал механизм виртуальных вызовов по своему усмотрению.
L>5. Массивы N-го порядка как массив из массиво N-1 порядка.
Только в паре с одноместным оператором []. В этом случае декомпозиция массива на подмассивы вытекает из строгой типизации.
Если же оператор[] может иметь произвольную арность — то можно трактовать такие массивы как гипер-прямоугольники.
Интересный подход к многомерным массивам в языке PL/I; там можно делать срезы по произвольному индексу, а не только по первому, как в С/С++.
L>6. Непрерывная область памяти + encode lambda expression.
То есть?
L>7. Прямоугольные/jagged/sparse arrays
jagged — это как раз массивы массивов (переменного размера).
Неплохо бы ввести два класса
— многомерные массивы (гиперпрямоугольники), в том числе разреженные
— иерархические (jagged)
Разница в том, что у первых можно делать срезы по произвольному индексу. Плюс всякие фишки с перестановкой размерностей(транспонирование).
L>8. ? L>9. синтаксис L>10. и в некотором сысле семантика... L>+ L>11. Вопросы оптимизации L>12. возврат\передача by value (в т.ч. массивов с неизвестным размером)
Больно дорогое это удовольствие — передавать по значению. Нужен механизм CopyOnWrite.
Вот, кстати, если бы COW вошёл в базис языка (как вошёл GC), это был бы плюс.
L>13. splice's L>14. способы итерации
Без разницы. Минимум, что нужно — произвольный доступ по индексу.
Даже не требуется вводить адресную арифметику на уровне языка — просто пишем обёртки-итераторы произвольного доступа, над которыми определяем адресную арифметику.
Так что любители работы с полуинтервалами в стиле STL не почувствуют ущерба.
Стоит разработать исчисление диапазонов (в т.ч. многомерных). Тогда foreach станет гармоничным. Чтобы можно было не только извлекать элементы, но и находить поддиапазоны.
L>15. любые мысли
Здравствуйте, Lande, Вы писали:
L>1. Массив как встроееный тип.
Нет
L>2. Массив как агрегат (а'ля С++).
Да
L>3. Непрерывное размещение элементов массива в памяти.
Скорее параметризовать массив типом менеджера памяти. Пусть он думает как расположены элементы и как получить i-й. Кстати при таком подходе разницы между массивом и списком уже не будет.
Ещё тогда можно делать разрежённые массивы, то есть получить массив всех чётных элементов без перераспределения памяти.
L>4. Совместимость с C++ (see 3)
Да, надо.
L>5. Массивы N-го порядка как массив из массиво N-1 порядка.
Спорно. Производительность пострадает. А если сделать управление памятью какое-нибудь и учеть пожелания пункта №3 то можно получать срез по любому индексу.
L>9. синтаксис
Предлагаю оператор индексации — [] и и итераторы .
L>Интересут все(на данном этапе ФЯ идут боком; да и массивы в ИЯ ортогональны), так как многие источники по language design умалчивают этот вопрос, либо довольствуются известными конструкцимя.
Я бы обощил всё что только можно. Например добавил опциональную возможность следить за изменениями элементов массива.
Здравствуйте, AndrewVK, Вы писали:
V>>Взять значение по индексу — идеально.
AVK>Это классическая то хеш-таблица? Ничего не путаешь?
Имеется в виду ключ, т.е. операции
Arr[i]
и
HashTable.Get(i)
совершенно эквивалентны
V>>Перебор значений — даже лучше, чем в классике (если в синтаксис добавить оператор ForEach), т.к., во-первых, в разреженном массиве не нужно анализировать пустоты, а во-вторых, оператор ForEach может служить синтаксической основой параллелизма. Единственная проблема — ForEach должен возвращать пару (индекс, значение).
AVK>А как быть с сохранением порядка?
Да уж, с этим проблема... ForEach — это действительно беспорядочная штука. Видимо, решение сдесь только одно — сделать упорядоченную выборку функцией такого "массива"
V>>Определение границ — из рук вон плохо. Но я, например, не припоминаю, когда и зачем мне такая фича была нужна. К тому же, что есть граница у многомерного массива?
AVK>А что такое определение границ?
Узнать максимальный индекс.
V>>Удаление значения — без проблем, если не забивать голову сдвигом хвоста на освободившееся место.
AVK>А забивать не надо, если мы претендуем на универсальность. А еще вопрос качественного хеш-кода тоде не так прост. А еще в хеше нельзя хранить повторяющиеся ключи.
В массиве, в общем, тоже два значения в одну ячейку не запихаешь.
Здравствуйте, AndrewVK, Вы писали:
V>>Узнать максимальный индекс.
AVK>И в чем проблема?
Тоже думаю, что ни в чём. Если массив в принципе не имеет ни верхней, ни нижней границы, то, соответственно, от него никак не получится добиться "Память не может быть Read" и, следовательно, отпадает необходимость ежесекундной проверки индекса на попадание в границы.
Здравствуйте, adontz, Вы писали:
L>>3. Непрерывное размещение элементов массива в памяти.
A>Скорее параметризовать массив типом менеджера памяти. Пусть он думает как расположены элементы и как получить i-й. Кстати при таком подходе разницы между массивом и списком уже не будет.
По скорости работы еще как будет.
A>Ещё тогда можно делать разрежённые массивы, то есть получить массив всех чётных элементов без перераспределения памяти.
L>>5. Массивы N-го порядка как массив из массиво N-1 порядка.
A>Спорно. Производительность пострадает.
Хм... А тебе не кажется, что в С массивы именно так и сделаны ? Нет ведь там многомерных массивов. Нет вообще. Двумерный массив есть массив из одномерных массивов. И никакая производительность не падает.
A>Предлагаю оператор индексации — [] и и итераторы .
ИМХО должно быть 2 типа
1. Массив в стиле С/C++. Т.е. пункт 3 — непрерывное размещение. Под этим также понимаю (пусть условно) массивы указателей на массивы и т.п. Для максимально высокого быстродействия. Что там ни говорите, а лучше, чем в С/C++ никто ничего не придумали и не придумает.
2. Обобщенный массив. Некий класс с перегрузкой operator[], итераторами и менеджером памяти. Для реализации всех и всяческих хитрых затей типа массива с четными только индексами, с хранением данных в Интернете и доступом через XML и т.п.
Кстати, в том же C# я бы добавил value-массив из value типов. Почему-то можно описать структуру или просто int, а вот массив структур или int — это уже класс с хранением в куче. Т.е.
int a0,a1,a2,a3,a4,... a99;
можно, и все в стеке
а вот
int a[100];
это уже System.Array и место ему в куче. Нелогично ИМХО.
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Кстати, в том же C# я бы добавил value-массив из value типов. Почему-то можно описать структуру или просто int, а вот массив структур или int — это уже класс с хранением в куче. Т.е.
PD>int a0,a1,a2,a3,a4,... a99;
PD>можно, и все в стеке
PD>а вот
PD>int a[100];
PD>это уже System.Array и место ему в куче. Нелогично ИМХО.
Зато можно
private struct IntBuffer
{
private fixed int a[100];
public int this[int index]
{
get { return a[index];}
set { a[index]=value; }
}
}
public void Test()
{
unsafe
{
IntBuffer buffer = new IntBuffer();
for(int i =0;i<100;i++)
buffer[i] = 2*i;
}
}
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Насколько я понимаю, это все же класс System.Array. В хипе он, а не в стеке. А хотелось бы все же в стеке. Да и без unsafe тоже бы не помешало.
ИМХО здесь именно тот момент, когда идеология, будучи последовательно примененной, вынуждает жертвовать здравым смыслом.
Кстати, есть и другой пример — когда идеологией пожертвовали в пользу здравого смысла. Я имею в виду string. Класс, но ведет себя порой как value — сравнение, инициализация.
Здравствуйте, Pavel Dvorkin, Вы писали:
A>>Скорее параметризовать массив типом менеджера памяти. Пусть он думает как расположены элементы и как получить i-й. Кстати при таком подходе разницы между массивом и списком уже не будет. PD>По скорости работы еще как будет.
В смысле не придётся создавать две совсем разные сущности. Вся разница уместиться в менеджер памяти.
A>>Спорно. Производительность пострадает. PD>Хм... А тебе не кажется, что в С массивы именно так и сделаны ? Нет ведь там многомерных массивов. Нет вообще. Двумерный массив есть массив из одномерных массивов. И никакая производительность не падает.
adontz wrote:
> A>>Скорее параметризовать массив типом менеджера памяти. Пусть он думает > как расположены элементы и как получить i-й. Кстати при таком подходе > разницы между массивом и списком уже не будет. > PD>По скорости работы еще как будет. > В смысле не придётся создавать две совсем разные сущности. Вся разница > уместиться в менеджер памяти.
С алгоритмической точки зрения std::vector (массив) и std::list (список) очень разные вещи. И не в менеджере памяти дело.
Или ты под массивом и списком понимаешь что-то другое?
> A>>Спорно. Производительность пострадает. > PD>Хм... А тебе не кажется, что в С массивы именно так и сделаны ? Нет > ведь там многомерных массивов. Нет вообще. Двумерный массив есть массив > из одномерных массивов. И никакая производительность не падает. > > А вот давай заглянем сюда — http://www.rsdn.ru/article/alg/2darray.xml
Но это сам язык не поддерживает, нельзя написать a[i,j,k], сравни с тем же паскалем. Поэтому и не делали встроенной
поддержки, т.к. легко можно сделать при необходимости.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, kan_izh, Вы писали:
_>С алгоритмической точки зрения std::vector (массив) и std::list (список) очень разные вещи. И не в менеджере памяти дело. _>Или ты под массивом и списком понимаешь что-то другое?
Да разные, но внешне вполне одинаковые.
На самом деле я каждый день крою создателей STL матом, потому что vector и list это УЖОС! Надо было list и linked_list! Сколько новичков прочтя в условии про список элементов писали std::list хотя там больше подходит std::vector. А сколько математиков пытались перемножить два std::vector?
_>Но это сам язык не поддерживает, нельзя написать a[i,j,k], сравни с тем же паскалем. Поэтому и не делали встроенной _>поддержки, т.к. легко можно сделать при необходимости.
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>Даже лучше алокаторы во много раз медленнее стека.
В каких случаях?
Эти аллокаторы делались с целью максимизации скорости в каком среднем сценарии использования. Возьмёмся максимизировать скорость в некотором частном случае и вуаля. Я ведь давал ссылку на статью, там вот как раз такой результат (хотя практически этот результат использовать не получится, потому что тогда будет хромать как раз вот тот средний случай).
)). Какими на Ваш взгляд должны бы быть встроенные в язык массивы? (А может и не надо "встроенности"? (std::array))
И не забывай про принцип наименьшей нежиданности.
Перекуём баги на фичи!
.
1.1.4 stable rev. 510
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
