LINUX.ORG.RU

[C/C++] выбор элемента списка без поиска по всему списку


0

2

Все добрых суток.

Допустим есть структура:

struct m{
     int id;
     int val;

     struct m *next;   // сразу добавил для работы в списке
};

Можно ли сделать обращение к элементу списка таких структур, таким же быстрым как к элементу массива, если я точно знаю номер элемента массива, id равно n+1'ому элементу массива.

К примеру

struct m arr[10]; // 10ть элементов 
struct m *list;   // указатель на первый элемент списка

Я знаю что мне нужен элемент с id = 5, тогда для массива я просто обращаюсь к элементу arr[4], для списка же мне придётся перебирать все элементы list пока я не найду нужный c id равным 5ти.

Можно ли как сразу обратиться к 5-му элементу?

Заранее спасибо!

★★★★★

ну, если расположить эти структуры последовательно... только тогда поле next не нужно и смысла во всём этом ровно ноль.

zph ()

Использовать массив. // К.О. № 1

Использовать дерево, но это уже не O(1). // К.О. № 2

geekless ★★ ()

> Я знаю что мне нужен элемент с id = 5

возможно вам нужен map<int,int>

aho ()

struct m *index[10];

ttnl ★★★★★ ()

Если для общего случая для id (любой) - то нет.

Если для частного случая (id всегда от 0 до 10 например). то надо сделать массив указателей на структуру, и заполнять его в зависимости от id.

Т.е. в начале все указатели - нули. Добавляется структура с id=2 - в массив[2] кладёшь указатель на структуру. list не нужен.

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

хотя list можно оставить. но всё равно за массивом надо следить, что-бы там «дохлых» указателей не оставалось.

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

10 элементов это для примера, по сути их будет много и не всегда одно и то же количество

думал делать через malloc, что то типа

for(int i = 0; i++; i < 10)
     memcpy(list,(u_char *) + i*(sizeof(struct m)), sizeof(struct m));

но уж больно криво

cyclon ★★★★★ ()

Можно оптимизировать

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

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

staseg ★★★★★ ()

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

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

>Если для частного случая (id всегда от 0 до 10 например). то надо сделать массив указателей на структуру, и заполнять его в зависимости от id.

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

anonymous ()

Можно ли как сразу обратиться к 5-му элементу?


нет.
если сразу то array, vector, map.

Boy_from_Jungle ★★★★ ()

Если id целые и идут подряд, и размер бол-мене известен, то вектор с запасом по длине и счетчик элементов. Если размер существенно меняется, то вектор с блочным выделением памяти (список векторов). Если id разреженные, то map.

Вы б задачу уточнили, а то вон народ уже велосипеды из списков указателей для Вас строить собрался;-)

AIv ★★★★★ ()

под линукс? выдели гиг виртуальной памяти и заполняй по мере необходимости в виде массива, а не списка :) или выдели полгига и сделай там массив указателей на ноды списка :)

arsi ★★★★★ ()

Если вы сделаете дополнительно struct m *list, то каждый раз, когда вы будете изменять список, вам придется в среднем по половине этого list перебирать, чтобы обновить его.

Допустим, удаляете вы m[5], для самого списка это делается элементарно и затрагивает лишь два соседних элемента, а вот чтобы обновить массив, придется перебирать все m[6]..m[end].

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

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

>Допустим, удаляете вы m[5], для самого списка это делается элементарно и затрагивает лишь два соседних элемента, а вот чтобы обновить массив, придется перебирать все m[6]..m[end].

У него, в исходном посте: «id равно n+1'ому элементу массива.». Значит ему всё равно придётся пересчитывать все id у всех последующих элементов.

Видимо, расчёт на то, что удаления не будет, или будет, но редко.

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

>Тогда проще массив сделать, а не список.

Мне, почему-то, кажется, что автор изобретает динамический массив:)

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

>думал делать через malloc, что то типа

for(int i = 0; i++; i < 10)

тут недавно тред был как раз про такую конструкцию.

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

тут недавно тред был как раз про такую конструкцию.

Ну, иногда такая запись к плохим вещам не приведет, например, вот два эквивалента:

for(i = -10; i < 0 ; i++)
и
for(i = -10; i++; i < 0)
(правда, во втором случае можно было бы i<0 и не писать =) ) Но, конечно, ни к чему хорошему такое не приведет...

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

> тут недавно тред был как раз про такую конструкцию.

Это где неудачник ныл о сложной ошибке, которую сложно обнаружить в коде?

anonymous ()

Можно ли сделать обращение к элементу списка таких структур, таким же быстрым как к элементу массива, если я точно знаю номер элемента массива, id равно n+1'ому элементу массива.

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

shty ★★★★★ ()

Тут все такие умные в std::map тычут забывая что map это красно-черное дерево и доступ там O(log(n))

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

> Тут все такие умные в std::map тычут забывая что map это красно-черное дерево и доступ там O(log(n))

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

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

Да тут уже сказали - хеш-таблица. В расширении stl есть готовая. Если id эти так и остантся численными то хеш значение и будет этот id по маске.

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

> Да тут уже сказали - хеш-таблица. В расширении stl есть готовая

да - есть, вообще контейнеров разных мастей полно, и все их авторы ссылаются на бенчмарки, что они быстрее всех, но у стандартного map есть один маленький плюс - он стандартный, хотя если конечно задача требует, и это оказывается узким местом - то не вопрос подобрать что-то на замену, но если у человека «10ть элементов» (с), то смысла использовать что-то нестандартное просто нет

aho ()

я вот так набыдлокодил себе(многое над переделать)):

struct J {
  char *name;
  unsigned int id;
};

struct Jarray {
  unsigned int Jc;
  struct J **Jv;
}
struct J *jnew() {
  struct J *newitem = malloc (sizeof (struct J));
  newitem->name = "anon";
  newitem->id = 0;
  return newitem;
}

struct Jarray *jarray_new () {
  struct Jarray *newarray = malloc (sizeof (struct Jarray));
  newarray->Jc = 0;
  newarray->Jv = malloc (sizeof (struct J*));
  *(newarray->Jv) = NULL;
  return newarray;
}

void jarray_append (struct Jarray *vector, struct J *item) {
  struct J **newvalue =  calloc (sizeof (struct J*), vector->Jc + 1);
  int i;
  for (i = 0; i < vector->Jc; i++) {
    *(newvalue + i) = *(vector->Jv + i);
  }
  *(newvalue + vector->Jc) = item;
  free (vector->Jv);
  vector->Jv = newvalue;
  vector->Jc += 1;
}

struct J *jget_by_num(struct Jarray *from, int i) {
  if (i >= from->Jc || i < 0)
    return NULL;
  return *(from->Jv + i);
}

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

> Да тут уже сказали - хеш-таблица. В расширении stl есть готовая. Если id эти так и остантся численными то хеш значение и будет этот id по маске.

А если элементов много больше чем число вариантов хэша, или если все id выьраны так что у них одно и то же хэш значение?;-)

ТС так задачу и не уточнил, так что соревнование «кто больше знает контейнеров и чей контейнер круче» толку не имеет - от задачи все зависит...

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

> Тут все такие умные в std::map тычут забывая что map это красно-черное дерево и доступ там O(log(n))

++

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