[нёх]О списке...

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

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

Есть ли имя собственное у структуры данных - контейнера, представляющего собой связный список массивов, собственно, хранящих элементы данных?

http://ru.wikipedia.org/wiki/Развёрнутый_связный_список

по моему, обычный двумерный массив (не путайте с матрицей/таблицей)

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

std::list<std::vector< ... > > ???

std::list<std::vector< ... > > ???

brutal facepalm

раз, два, три (длина массивов здесь является фиксированной последовательностью)

ну и вот, если ещё не обратил внимания

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

массив отличается от связанного списка

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

> Речь идет не о способе хранения, а о конкретном наборе данных.

У кого идёт речь?

Есть ли имя собственное у структуры данных

вопрошает ТС.

В этой задаче

В какой?

Спасибо Кошмару и Ктулху Жтутфу за наводку на «unrolled», и за «VList» в частности (собственно, похоже, вчера вплотную подобрался к этой структуре, но отмел геометрическую прогрессию роста размеров массивов в пользу арифметической, дабы память не жрало)

> в ещё более долбоёонутой форме, чтобы никто ничего непонял

ТС спрашивает как одним словом назвать «связный список массивов»

одним словом - Х***я

Вы сначала на его ник посмотрите.

Чего только люди не придёмают, лишь бы не занятся сексом с девушкой

> brutal facepalm

А чего, дяденька, шаблоны и stl разве не для того придумали?

> вы мне еще таки скажите, что массив отличается от связанного списка.

Вообще то в массиве данные добавлять/удалять/менять местами гораздо дороже чем в списке. Хотя с другой стороны, с учетом архитектуры совр. компов для ряда задач эффективней заранее выделить массив необходимой длины и ввести в нем отдельный счетчик на число элементов - получается довольно эффективное добавление/удаление и хороший обход. С третьей стороны, хорошие списки почти так и устроены;-)

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

В исходном посте ЯП не указан -> подходит любой.

Вопрос о реализации и правда не стоял, но мне, как не-программисту вопрос показался неск странным - от названия одним словом содержание должно как то изменится?

Удобнее в речи использовать термин чем описание.

Ну ты же, как не-программист, очень редко (или вообще не) называешь свои харды накопителеями на жестких магнитных дисках?

Вот и у программистов... Вместо: «объектно-ориентированная реализация глобальных переменных», или там: «объект, создающий себя в единственном экхемпляре» зовем просто - синглтон по-метропольному, или «одиночка» по-русски. Или, скажем, напишешь: «V-список» - и сразу станет понятно, о чем идет речь.

А.Н.Крылов (кораблестроитель) по поводу появившегося тогда тензорного исчисления написал 'надо экономить мозги, а не бумагу'. Список массивов звучит не сильно длиннее чем V-список, но человеку со стороны (напр не-программисту типа меня) ИМНО куда понятнее.

Термин хард распространен так же как и НЖМД. Мне вот интересно, сколько программистов поймет сходу что есть V-list? Проведу ка по знакомым опрос...;-)

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

>НЖМД
А чой то мы сразу после громкой цитаты бумагу бесстыдно продолжаем иканомить? :)

Мне вот интересно, сколько программистов поймет сходу что есть V-list?

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

Потом, если позволишь, вернемся к
std::list<std::vector< ... >>

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

Вот давай и рассмотрим std::list<std::vector< ... >> с четырех сторон:
* std::list<std::vector< ... >> - длина списка строго 1, длина массива N. Это обыкновенный линейный массив. Мы можем обратиться к любому элементы массива за одно действие. А попробовав последовательно добавить еще N элементов мы столкнемся с необходимостью N раз выделить память под массив нового (на 1 большего) размера и соответственно, с необходимостью N раз скопировать содержимое старого массива в новый, в итоге затратив около N*N операций.

* std::list<std::vector< ... >> - длина списка N, длина массива строго 1. Теперь это обыкновенный список. Теперь, чтобы обратиться к любому элементу структуры нам необходимо будет совершить до N действий. Зато последовательное добавление еще N элементов будет выполнено всего за N операций.

* std::list<std::vector< ... >> - длина списка A, длина массива строго B, A*B >= N. Это развернутый список. Мы получили вроде бы такой же список, как и в предыдущем примере, но теперь для доступа к элементу достаточно совершить всего A операций! А для последовательного добавления еще N элементов теперь достаточно будет совершить те же N операций. По-моему, неплохо для такого небольшого изменения?

* std::list<std::vector< ... >> - длина списка log N, длины массива образуют геометрическую прогрессию; например - 2,4,8,16... Это и есть наш V-список. Теперь, чтобы получить доступ к любому элементу, потребуется log N операций (для указанной прогрессии и N=350 000 000 доступ к любому элементу списка потребует максимум 29 шагов), ну и добавление нового элемента в структуру все еще требует всего одного действия. Вроде бы разницы с предыдйщим примером не видно? Но она есть: в общем случае log N < A. Например, увеличение нашего списка из 350 000 000 элементов в 4 раза увеличит кол-во шагов для доступа в предыдущем примере тоже в 4 раза, а для V-списка кол-во шагов увеличится с 29 до 33 шагов.

Ччорт, для одного std::list<std::vector< ... >> придумали 4 разных названия :)

Так какой именно std::list<std::vector< ... >> ты имел в виду? :)

У меня наверное не хватает воображения, но такая конструкция (ежели уж она используется) предполагает что элемент адресуется парой - элемент списка:позиция в векторе.

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

Но когда говорят список или массив обычно подразумевают вполне определенную организацию данных и вполне определенные алгоритмы работы с ними, как раз реализованные в частности в STL (ИМНО).

ЗЫ спросил у соседа (наст программист и гуру) про V-list - не знает, считает список массивов куда наглядней. Кстати что есть СВЯЗННЫЙ СПИСОК (точнее, если говорить связный список, то подразумевается что и есть не связный список - это вообще как;-))?

Когда грят «связный», то подразумевают, о наличии связи с другим(-и) элементом(-ами) - соседним, например. В реализации такая связь может быть представлена указателем. А вообще список может быть реализован и на линейном массиве - там связь вроде как и не нужна ввиду упорядоченности.

У меня наверное не хватает воображения, но такая конструкция (ежели уж она используется) предполагает что элемент адресуется парой - элемент списка:позиция в векторе

Вчера прототип для переноса в Mono накидал. Вот как можно адресовать список массивов банальным индексом без всяких пар. Ничего что на поцкале? :)

type
  // Список массивов - по сути, аналог list<vector<int>>
  PItem = ^TItem;
  TItem = record
    Next: PItem;
    Data: array of Integer;
  end;

  VList = class
  public
    Head: PItem;
    Length: Integer;
    R, Pw: LongInt;
  public
    constructor Create;
    destructor Destroy; override;

    function Count: Integer;
    function At(offset: Integer): Integer;
    procedure Add(x: Integer);
  end;

constructor VList.Create;
begin
  Head := nil;
  Length := 0;
  R := 0;
  Pw := -1;
end;

function VList.At(offset: Integer): Integer;
var p: PItem; m, j: Integer;
begin
  p := Head;
  // Это мы считаем, сколько конкретно надо
  // переходов по списку сделать, для половины элементов m = 0
  m := Round(Trunc(ln(offset+1) / ln(2))); // ~log2 offset
  for j := 1 to (Pw - m) do p := p^.Next; // a^.b аналог a->b
  result := p^.Data[offset + 1 - (1 shl m)] // shl это как << в Си
end;

procedure VList.Add(x: Integer);
var p: PItem;
begin
  if (Length+1) > ((R shl 1)-1) then begin
    New(p);
    p^.Next := Head;
    if R = 0 then R := 1 else R := R shl 1;
    Inc(Pw); // по сути (Pw+1) - кол-во элементов списка
    SetLength(p^.Data, R);
    Head := p;
  end;
  Inc(Length);
  Head^.Data[ Length - R ] := x;
end;

Ну дак в int аж 32 бита (у меня на платформе), конечно туда можно много напихать;-)

Насчет связности - Вы ж сами сказали, что есть данные, а есть алгоритмы работы с ними... Если список рассматривать как данные организованные определенным образом, скажите то есть НЕСВЯЗНЫЙ список? Массив это все таки массив, конечно массив можно использовать как список а список как массив, но это уже к алгоритмам.

Ты, наверное, не придал одному слову должного значения, так что повторю его: «связь»

СВЯЗЬ. То, что связывает, соединяет что-нибудь с чем-нибудь; отношение, создающее что-нибудь общее между чем-нибудь,

Понятие «списки» включает в себя самые разные структуры данных. Это могут быть и массивы, в том числе массивы записей, и специальные динамические структуры данных, и даже деревья. Общим для них является то, что они содержат набор записей одного вида, ограниченный по размеру или неограниченный, упорядоченный или неупорядоченный. Данные, хранящиеся в этих записях, обычно логически связаны между собой, например, фамилии студентов одной группы и т.п. В тексте программы такая связь может выражаться в том, что все такие элементы хранятся в одном и том же массиве как непрерывном блоке памяти. Но кроме общего имени массива (и адреса его начала) между этими элементами никакой другой физической связи нет, и на физическом уровне подобные списки могут быть названы «несвязными» (или, что (почти) то же самое, «несвязанными»). Т.е. внутри них нет связей (их элементы не связаны друг с другом физически). Типичным примером незвязного (физически) списка является массив.

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

>Я знаю два контейнера
А, ну тогда несвязных списков просто нет :) , а словом связность обозначают конкретное вол-во указателей (1 - просто связный, 2 - двухсвязный, k - к-связный)

>Но я не знаю что есть связный список, потому что из такого термина следует существование несвязного списка

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

А еще я видел программу концерта на бумаге, и ее тоже можно назвать программой? А еще я видел указатель на щите «Москва 100км», его тоже будем называть указателем? А еще я видел вектор (палочка со стрелочкой) и массив (лесной, из деревьев).

Вроде как форум посвящен программированию, ТС спрашивал про КОНТЕЙНЕР-СВЯЗНЫЙ СПИСОК. Список есть устоявшийся термин в программировании, вот я и хочу узнать - что есть несвязный список? Массив (вектор) это тоже устоявшийся термин, и это не то же самое что список. Несвязный список это массив? Это типа официяльная терминология, да?

Мне как то пофик на термины всегда было, но тут любопытство заело, тем более топик о терминологии как раз... вдруг че нового узнаю;-)

> А, ну тогда несвязных списков просто нет :) , а словом связность обозначают конкретное вол-во указателей (1 - просто связный, 2 - двухсвязный, k - к-связный)

Интересная гипотеза;-)

> А еще я видел программу концерта на бумаге, и ее тоже можно назвать программой?

Да. Программа - это последовательность инструкций для исполнителя, которым может быть хоть JUGENE, хоть дрессированный таракан.

Список есть устоявшийся термин в программировании, вот я и хочу узнать - что есть несвязный список?

Простая последовательность элементов.

Массив (вектор) это тоже устоявшийся термин, и это не то же самое что список. ... Несвязный список это массив?

Массив - это способ реализации простого списка.

>вот я и хочу узнать - что есть несвязный список?

list or sequence is an abstract data structure that implements an ordered collection of values...

Меню в ресторане - вполне себе список. Более того, как раз 0-связный(так понятнее) - если там не напишут «это лучше всего употреблять с тем-то».

Массив (вектор) это тоже устоявшийся термин, и это не то же самое что список. Несвязный список это массив?

Почему вдруг? «массив», «вектор» и т.п. есть 0-связный список, но не наоборот. Какой-нибудь /dev/ttyS0, наверное, тоже (данные там есть, идут они последовательно, и при этом связей между ними нет).

Ок;-)