как бы лучше всего(самый быстрый способ) реализовать съеживание массива:
у нас есть массив(можно вектор) с разреженным заполнением,
известны индексы каждого елемента и известно количество элементов нужно поместить в массив из точного количества элементов

int _tmain(int argc, _TCHAR* argv[])
{
    vector<int>    Test, Test1;
    
    DWORD start = GetTickCount();
    Test.resize(1600000);
    for (int i= 0; i< 1600000; ++i)
        if(i%2)
            Test[i] = i+1;
    
    Test1 = Test;//???

    DWORD stop = GetTickCount();

    std::cout << "my time: " << (stop - start) << std::endl;
    return 0;
}

Здравствуйте, sonsen, Вы писали:

S>как бы лучше всего(самый быстрый способ) реализовать съеживание массива:
S>у нас есть массив(можно вектор) с разреженным заполнением,
S>известны индексы каждого елемента и известно количество элементов нужно поместить в массив из точного количества элементов

Чем не устраивает resize с последующим копированием?

Здравствуйте, Bell, Вы писали:

B>Здравствуйте, sonsen, Вы писали:

S>>как бы лучше всего(самый быстрый способ) реализовать съеживание массива:

B>Чем не устраивает resize с последующим копированием?

Можно примерчик?

Здравствуйте, sonsen, Вы писали:

B>>Чем не устраивает resize с последующим копированием?

S>Можно примерчик?

Вот так

Test1.resize(16000/2);
for(int i=0, j=0; i!=16000; i+=2, j++) // когда мы знаем, как прыгать по элементам
  Test1[j] = Test[i];

Или вот так — более общий подход

Test1.reserve(16000/2); // ничего страшного, если слегка ошибёмся - это ж только резервирование
Test1.resize(0);
for(int i=0; i!=16000; ++i)
  if(i%2==0) // когда мы изначально не знаем, как прыгать - и только проверяем условие
    Test1.push_back(Test[i]);

Можно ещё припахать STL (и boost/iterator) — но там будет нечто громоздкое. Потому воздержусь.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, sonsen, Вы писали:

B>>>Чем не устраивает resize с последующим копированием?

К>Можно ещё припахать STL (и boost/iterator) — но там будет нечто громоздкое. Потому воздержусь.

Я тут как бы проводил замеры, поскольку требования к скорости наиболее критичны, и нашел что
vector.push_back() работает в полтора раза медленнее,чем vector[] (ну это и понятно ...)

А вот если иметь дело с map, то разница уже в 20 раз и более (включена оптимизация по скорости /02 и /Ot)

И еще вопрос, может кто нибудь знает где найти perfect hash ф-ю (это такая у которой нет коллизий) для строк, если известен заранее диапазон возможных hash значений . Я тут нашел один проект, но как я понял хэш ф-я генерится в compile time, а мне надо в реальном времени.

Здравствуйте, sonsen, Вы писали:

S>как бы лучше всего(самый быстрый способ) реализовать съеживание массива:
S>у нас есть массив(можно вектор) с разреженным заполнением,
S>известны индексы каждого елемента и известно количество элементов нужно поместить в массив из точного количества элементов

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

Здравствуйте, sonsen, Вы писали:

S>Я тут как бы проводил замеры, поскольку требования к скорости наиболее критичны, и нашел что
S>vector.push_back() работает в полтора раза медленнее,чем vector[] (ну это и понятно ...)

Даже с предварительным reserve?

S>А вот если иметь дело с map, то разница уже в 20 раз и более (включена оптимизация по скорости /02 и /Ot)

А зачем тебе map?

S>И еще вопрос, может кто нибудь знает где найти perfect hash ф-ю (это такая у которой нет коллизий) для строк, если известен заранее диапазон возможных hash значений .

Может быть хотел сказать "если известен заранее набор всех возможных входных строк" ?
Если это не так, то гарантировать отсутствие коллизий невозможно

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Если индексы упорядочены по возрастанию, то новый массив заводить не обязательно. Просто перетаскиваешь элементы к началу, а потом resize.

А если наплевать на упорядочение, то можно ещё и сэкономить на переносах.

Эскиз:

bool keep(int i) { return i%2==0; }

int i=0, j=n-1;
while(i < j)
{
  while(i<j &&  keep(i)) ++i;
  while(i<j && !keep(j)) --j;
  // arr[i] свободно, arr[j] содержательно - переносим!
  if(i<j) arr[i++] = arr[j--]; // или swap, если swap дешевле копирования
}
arr.erase(arr.begin()+j+1, arr.end());

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

Здравствуйте, Bell, Вы писали:

B>Здравствуйте, sonsen, Вы писали:

S>>Я тут как бы проводил замеры, поскольку требования к скорости наиболее критичны, и нашел что
S>>vector.push_back() работает в полтора раза медленнее,чем vector[] (ну это и понятно ...)

B>Даже с предварительным reserve?

C reserve, как ни странно, у меня вылетел assert .... на 1 600 000 элементов, а с resize нет. Может что-то где-то напутал, код позже

B>А зачем тебе map?

Мне нужна быстрая вставка и быстрый поиск, два условия наиболее критичных. Причем вставка только один раз в массив, удаление и вставка после не требуется. Проанализировав AVL, красночерные деревья, понял что хеш будет круче всего.
Парсится файл (мы знаем его размер), и следовательно можем заресайзить массив сразу на размер файла. Считаем хеш от каждого слова и вставляем в массив (хеш это индекс). Если подобрать perfect hash для заданного диапазона то все строки попадут в массив в сортированном! виде. Далее съеживаем массив и ресайзим — в результате мы получаем сортированный массив с экономией памяти, где сложность вставки O(1), сложность поиска O(2). Теперь чтобы получить искомый элемент:

if (array[n - emptyCells] == hashToFind)
  return true;
else 
  return false;

S>>И еще вопрос, может кто нибудь знает где найти perfect hash ф-ю (это такая у которой нет коллизий) для строк, если известен заранее диапазон возможных hash значений .

B>Может быть хотел сказать "если известен заранее набор всех возможных входных строк" ?
B>Если это не так, то гарантировать отсутствие коллизий невозможно

Из-за размера файлв мы можем гарантирвать что количство строк (слов), не превысит размер массива

как называется операция обратная "съеживанию" %)

Здравствуйте, zaufi, Вы писали:

Z>как называется операция обратная "съеживанию" %)
Разглаживание? Раздувание? Разбавление?

Здравствуйте, zaufi, Вы писали:

Z>как называется операция обратная "съеживанию" %)
Раскукоживание

Z>как называется операция обратная "съеживанию" %)
разреживание?

Здравствуйте, Warturtle, Вы писали:

W>Здравствуйте, zaufi, Вы писали:

Z>>как называется операция обратная "съеживанию" %)
W>Раскукоживание
мне приходило на ум "разъеживание"... но твой вариант the best!

Warturtle пишет:

> Z>как называется операция обратная "съеживанию" %)
> Раскукоживание

Ну, нет ! Раскукоживание -- это операция, обратная
скукоживанию, а у нас речь идёт о съёживании, это ж
совсем другая операция!

Здравствуйте, zaufi, Вы писали:

Z>как называется операция обратная "съеживанию" %)
Очевидно, разъёживание.