struct point
{
double x;
double y;
};
struct st1
{
. . .
list<int> n;
list<point> p;
};
class MyFile
{
. . .
list <st1> records;
};
скорость списка
Доброго времени суток! Имею удовольствие работать с базой данных с двумя-тремя тыс. записей, которую желательно считать в память из бинарного файла. Сначала юзал new/delete, все более-менее работало :), но где-нибудь обязательно за границу массива вылезало. Решил использовать list. Получилось примерно так:
Получилось так, что при использовании указателей 3000 записей читались за секунду, а со списками на это уходит секунд 30, да еще и памяти мегабайт 60.
Вопрос 2:
Есть много double значений типа 709454.2682, причем первые несколько цифр одинаковы (в данном случае - 709). Как максимально быстро в массиве найти количество этих цифр и оставить только правую часть? Всем спасибо!
Код:
Получилось так, что при использовании указателей 3000 записей читались за секунду, а со списками на это уходит секунд 30, да еще и памяти мегабайт 60.
Вопрос 2:
Есть много double значений типа 709454.2682, причем первые несколько цифр одинаковы (в данном случае - 709). Как максимально быстро в массиве найти количество этих цифр и оставить только правую часть? Всем спасибо!
Если можно использовать массивы - используй их, это часто оптимальнее всего, если конечно он не занимает десятки метров в памяти, тогда загрузка будет дольше. Так что я бы поискал ошибки с границами массива.
Цитата:
Как максимально быстро в массиве найти количество этих цифр и оставить только правую часть?
Используй индексы, как делают БД. При добавлении/изменении записей обновляй по ходу индекс, при поиске значений ищи их по индексу, это будет намного быстрее перебора.
В данном случае, например, можно иметь массив вида Index[prefix] = array of ID, где prefix - все возможные значения первых 3х цифр, которые ты собираешься искать. Каждая запись массива содержит ID (или какая у тебя адресация в БД) записи, у которой это поле начинается с prefix.
Доработай под свою задачу.
Цитата: plastictown
Получилось так, что при использовании указателей 3000 записей читались за секунду, а со списками на это уходит секунд 30, да еще и памяти мегабайт 60.
Почему list, а не vector? vector, в общем случае, можно так же быстро считать, как и динамически выделенный массив. Ну и код чтения не был приведён, чтобы что-то сказать наверняка.
Цитата: plastictown
Вопрос 2:
Есть много double значений типа 709454.2682, причем первые несколько цифр одинаковы (в данном случае - 709). Как максимально быстро в массиве найти количество этих цифр и оставить только правую часть? Всем спасибо!
Есть много double значений типа 709454.2682, причем первые несколько цифр одинаковы (в данном случае - 709). Как максимально быстро в массиве найти количество этих цифр и оставить только правую часть? Всем спасибо!
Тут в общем случае тоже сразу не видно как решать, да и не совсем ясно что значит "оставить только правую часть". Правую часть числа или массива?
Если допустим перевод в int, то можно поломать голову (или, например, домножить на коэффициент 10000 и перевести в какой-нибудь long long int). Иначе пока не вижу другого подхода, кроме как переводить в строку.
Понятие скорость списка - понятие растяжимое. Есть скорость добавления элемента - у списка оно постоянно и весьма мало, есть скорость поиска элемента - у списка оно линейно, есть скорость удаления - у списка хорошее, есть скорость последовательного извлечения - у списка оно тоже хорошее. Что касается вектора, то, в общем случае, скорость добавления в него может быть гораздо хуже чем у списка. Это в том случае, если заранее не резервировать место под добавления большого кол-ва элементов. А скорость удаления элемента - всегда хуже чем у списка, ну разве за исключением случая удаления последнего элемента.
Так что в некоторых случаях - список рулит, в некоторых вектор, и говорить что список - отстой, а вектор рулит, в общем случае нельзя.
Что касается второго вопроса, то можно сделать так.
a. переводим числа в строковое представление.
b. принимаем длину первой строки за искомую длину левой части, обозначим её как L.
c. Пробегаем по всем элементам массива, каждый раз вычисляя длину совпадающего начала текущеё строки и первой строки до длины не превышающей L(обозначим как L1) и, если L1<L, то L=L1. Если L==0, то дальше можно не искать.
Так что в некоторых случаях - список рулит, в некоторых вектор, и говорить что список - отстой, а вектор рулит, в общем случае нельзя.
Что касается второго вопроса, то можно сделать так.
a. переводим числа в строковое представление.
b. принимаем длину первой строки за искомую длину левой части, обозначим её как L.
c. Пробегаем по всем элементам массива, каждый раз вычисляя длину совпадающего начала текущеё строки и первой строки до длины не превышающей L(обозначим как L1) и, если L1<L, то L=L1. Если L==0, то дальше можно не искать.
Цитата: loki231
Так что в некоторых случаях - список рулит, в некоторых вектор, и говорить что список - отстой, а вектор рулит, в общем случае нельзя.
А кто это говорит? Тут не общий, а конкретный случай. Вектор является наиболее близким аналогом динамически выделяемого массива. Зарезервировал нужное количество ячеек и добавляй. Или выделил сколько нужно памяти и махом считал весь файл (правда, если тут string и прочие хитрые типы, то это не тот случай).
Цитата: Kogrom
Тут в общем случае тоже сразу не видно как решать, да и не совсем ясно что значит "оставить только правую часть". Правую часть числа или массива?
Если допустим перевод в int, то можно поломать голову (или, например, домножить на коэффициент 10000 и перевести в какой-нибудь long long int). Иначе пока не вижу другого подхода, кроме как переводить в строку.
Если допустим перевод в int, то можно поломать голову (или, например, домножить на коэффициент 10000 и перевести в какой-нибудь long long int). Иначе пока не вижу другого подхода, кроме как переводить в строку.
Правая часть это именно то, что не повторяется в каждом значении. Про строку я и сам думал, но что-то мне подсказывает, что это не лучший вариант:)
Что касается кода, да, каюсь. Код на работе, а я -дома. Опишу вкратце:
Код:
Record rec; //Экземпляр записи, в который считываются даные
list<Record> records; //Список записей
// Очистка списков rec
. . .
//Чтение заголовка записи постоянного размера при помощи ReadFile()
. . .
//Чтение данных о числе точек в записи
. . .
// Чтение данных в rec
. . .
//Добавление rec в список
records.insert(в_конец, rec);
list<Record> records; //Список записей
// Очистка списков rec
. . .
//Чтение заголовка записи постоянного размера при помощи ReadFile()
. . .
//Чтение данных о числе точек в записи
. . .
// Чтение данных в rec
. . .
//Добавление rec в список
records.insert(в_конец, rec);
а нельзя использовать бд? sqlite к примеру или ms sql server compact... бо такое ощущение, что пахнет велосипедом...
Цитата: Artem_3A
а нельзя использовать бд? sqlite к примеру или ms sql server compact... бо такое ощущение, что пахнет велосипедом...
Хорошая идея. Но может автору самому интересно его изобрести :)
Про индекс для поиска значений - если цифры всегда будут 6-ти ззначными (709454), то делишь её на 1000, иначе преобразуешь в строку и берёшь первые 3 символа. Потом полученное число используешь как индекс для массива. Элемент массива может либо содержать набор указателей на полные записи элементов, либо, если всегда нужно будет только знать количество элементов с такими 3-мя первыми цифрами - то просто ulong.
Легко реализовать и быстрый поиск. При изменении записей просто делай +/- 1 у соответствующего элемента индекса.
Такой варинат будет в любом случае быстрее, чем искать элементы в ходе работы проги.
Цитата: plastictown
Правая часть это именно то, что не повторяется в каждом значении. Про строку я и сам думал, но что-то мне подсказывает, что это не лучший вариант:)
Всё равно не ясно. А если у нас числа 709454.2682 и 7094.2682, то будем 7094 откидывать? А если 709454.2682 и 7094.5482, то 709454 будем?
Условие нечётко формулируешь. Сформулировал бы чётко, давно решил бы сам с помощью каких-нибудь frexp, ldexp, домножений на коэффициент и битовых масок... А так, в общем виде - преобразовывай в строку.
Цитата: plastictown
Что касается кода, да, каюсь. Код на работе, а я -дома. Опишу вкратце
Думаю в коде что-то лишнее, ну и list на vector надо всё-таки заменить. Что мешает попробовать? Ну и векторовское reserve не помешает, наверное.
Всем спасибо за кучу идей, дальше сам постараюсь. По 1-му вопросу основная загвоздка в том, что число записей в файле заранее не известно, поэтому выделять память не очень удобно. Решил поднатужиться и пересчитать для начала записи.
Что касается второго вопроса, то количество цифр в числах одинаково.
Вот.:D
Что касается второго вопроса, то количество цифр в числах одинаково.
Вот.:D
Переделал с vector вместо list. Скорость чтения стала вполне приемлемая, а вот памяти хавает очень много. 100 кБ (600 записей) файл считываю в память, 30 метров куда-то деваются. Даже если машина и даст 500-600 метров под большой файл, все равно это чересчур. Наверное придется выложить завтра проект, может кто-нибудь посмотрит:)
Написал empty() вместо clear(). В этом была проблема:D А насчет второго вопроса я просто вычел из каждого элемента минимальный и получил практически то, что было нужно.