Давеча на собеседовании был спрошен в контексте правильной стратегии использования памяти: - Если есть набор данных (например, аналитика) и их нужно обработать, то какая организация данных оптимальнее: структура массивов или массив структур?
Вообще их требования к вакансии на удивление точно совпадали с моими скиллами в резюме.
Я даже удивился, как такое бывает. Обычно кандидат подгоняет резюме под вакансию, а не наоборот
Каюсь, я конкретного ответа на вопрос не дал, ибо для меня было недостаточно вводных данных в вопросе.
За что через 5 минут после начала интервью был признан незнающим организацию компьютерной памяти, на чем интервью и закончилось.
Поэтому прошу всезнающих коллег объяснить мне, какой должен быть правильный ответ.
ЗЫ:
В самой конторе (банк из первой сотни, кстати):
1. Девочка на ресепшене искала себе другую работу прямо на рабочем месте (говорила по телефону с агентами).
2. Сотрудница по персоналу со мной не поздоровалась, украдкой посмотрела в лицо, все как-то бочком-бочком и с глубоко несчастным видом.
3. Мощный интервьюер не рассказал чем они там таким архиважным занимаются, что стоят перед проблемой выбора структур массивов и массивов структур, но зато после собеседования при мне кинул мое резюме в шредер привычным жестом. На прощание он руки мне не подал. Тоже расстроился, наверное, как и сотрудница по персоналу.
В общем, конторе еще учиццо и учиццо уважительному отношению к посетителям.
Как клиента они меня не получат никогда!
lgb>- Если есть набор данных (например, аналитика) и их нужно обработать, то какая организация данных оптимальнее: структура массивов или массив структур?
Здравствуйте, wamaco, Вы писали:
W>Здравствуйте, lgb, Вы писали:
lgb>>- Если есть набор данных (например, аналитика) и их нужно обработать, то какая организация данных оптимальнее: структура массивов или массив структур?
W>структура массивов
Здравствуйте, LuciferSaratov, Вы писали:
lgb>>В самой конторе (банк из первой сотни, кстати): LS>ну так сообщи имя героя (название компании), чего стесняешься-то?
lgb>>>- Если есть набор данных (например, аналитика) и их нужно обработать, то какая организация данных оптимальнее: структура массивов или массив структур?
W>>структура массивов
lgb>Без подробностей?
потому как, с точки зрения обработки аналитики удобнее и проще обрабатывать однотипные данные (массивы),
нежели обработать упорядоченный набор данных (массив) сложные типы данных (структуры)!
пример, дерево!
простейший случай — структура (ветви) данных (значения)
представьте, массив деревьев! ужос и бред!
+ еще структура может описывать аналитические интегральные данные, данные как раз агрегируются в конечных массивах!
Здравствуйте, lgb, Вы писали:
W>>структура массивов
lgb>Без подробностей?
Это называется columnar format. В последнее время все чаще используется на разных Big-Data\Hadoop платформах. См. формат Parquet например.
1) Если данные помещаются в память то итерируя по одному-двум полям ты будешь работать с локализованными данными и процесор чаще будет попадать в кэш.
2) Если не помещаются — то однин из массивов (колонку БД например) может таки поместиться в память, а если нет то все равно влезет больше элементов чем в массиве структур. Соответственно реже будешь читать данные с дисков. Плюс к тому же см (1).
3) Можно менять схему\структуру без переформатирования данных на дисках.
Здравствуйте, lgb, Вы писали:
lgb>Давеча на собеседовании был спрошен в контексте правильной стратегии использования памяти: lgb>- Если есть набор данных (например, аналитика) и их нужно обработать, то какая организация данных оптимальнее: структура массивов или массив структур?
lgb>Поэтому прошу всезнающих коллег объяснить мне, какой должен быть правильный ответ.
Простой ответ (практика) — делаем слой абстракции (например на шаблонах, 0 оверхеда), реализуем оба варианта, сравниваем производительность
Нормальный ответ (теоретика) — данные к которым нужен доступ должны лежать рядом.
Если надо экономить память — то тоже лучше структура массивов, не надо тратиться на выравнивание.
Если надо обработать только одно поле, то с точки зрения кеша и всяких префетчей в процессоре лучше структура массивов.
С точки зрения распараллеливания (в т.ч. simd) — тоже лучше работать с массивами.
Но если надо обращаться сразу ко всем полям записи, и соседние записи не нужны — то массив структур.
Ответ разработчика из Сколково — пишем как удобнее (массив структур), потом заводим тикет на исследование возможностей повышения производительности.
Умный ответ — "а зачем велосипед городить? вы же наверняка такую задачу уже решали, производительность разных подходов замеряли, код писали — вот его и реюзнем".
Здравствуйте, wamaco, Вы писали:
W>потому как, с точки зрения обработки аналитики удобнее и проще обрабатывать однотипные данные (массивы), W>нежели обработать упорядоченный набор данных (массив) сложные типы данных (структуры)!
Это из области угадай о чем я думаю...
Для меня структура массивов подразумевает — некую структуру — содержащие разные массивы данных.
Массив структур вполне может быть представлением таблицы базы данных.
W>пример, дерево! W>простейший случай — структура (ветви) данных (значения)
Пример из под палки.
W>представьте, массив деревьев! ужос и бред!
А если структура вполне может содержать массивы структур?
W>+ еще структура может описывать аналитические интегральные данные, данные как раз агрегируются в конечных массивах!
W>отсюда -> структура массивов
Здравствуйте, D. Petrov, Вы писали:
DP>1) Если данные помещаются в память то итерируя по одному-двум полям ты будешь работать с локализованными данными и процесор чаще будет попадать в кэш. DP>2) Если не помещаются — то однин из массивов (колонку БД например) может таки поместиться в память, а если нет то все равно влезет больше элементов чем в массиве структур. Соответственно реже будешь читать данные с дисков. Плюс к тому же см (1). DP>3) Можно менять схему\структуру без переформатирования данных на дисках.
По сути идет оптимизация чтения одного-нескольких полей из базы данных. Это выгодно в тех задачах, когда редко интересен полных набор полей. Интересный подход.
Вы описываете преимущества структуры массивов — но про преимущества массивов структур ни слова.
Но не правильно утверждать, что одно лучше другого. Все зависит от поставленной задачи.
Здравствуйте, Abyx, Вы писали:
A>Простой ответ (практика) — делаем слой абстракции (например на шаблонах, 0 оверхеда), реализуем оба варианта, сравниваем производительность
A>Нормальный ответ (теоретика) — данные к которым нужен доступ должны лежать рядом. A>Если надо экономить память — то тоже лучше структура массивов, не надо тратиться на выравнивание. A>Если надо обработать только одно поле, то с точки зрения кеша и всяких префетчей в процессоре лучше структура массивов. A>С точки зрения распараллеливания (в т.ч. simd) — тоже лучше работать с массивами. A>Но если надо обращаться сразу ко всем полям записи, и соседние записи не нужны — то массив структур.
A>Ответ разработчика из Сколково — пишем как удобнее (массив структур), потом заводим тикет на исследование возможностей повышения производительности. A>Умный ответ — "а зачем велосипед городить? вы же наверняка такую задачу уже решали, производительность разных подходов замеряли, код писали — вот его и реюзнем".
Есть еще операции добавления и удаления.
В место того чтобы обновить 1 массив, приходится обновлять сразу несколько.
Здравствуйте, lgb, Вы писали:
lgb>Давеча на собеседовании был спрошен в контексте правильной стратегии использования памяти: lgb>- Если есть набор данных (например, аналитика) и их нужно обработать, то какая организация данных оптимальнее: структура массивов или массив структур? lgb>Каюсь, я конкретного ответа на вопрос не дал, ибо для меня было недостаточно вводных данных в вопросе. lgb>За что через 5 минут после начала интервью был признан незнающим организацию компьютерной памяти, на чем интервью и закончилось. lgb>Поэтому прошу всезнающих коллег объяснить мне, какой должен быть правильный ответ.
по существу:
правильный ответ — "а мы покупаем, или продаем?". примеры:
если нужно выполнить запрос типа (from p in points select p.x where p.y == 123) — быстрее отдельно хранить массив всех p.y, т.к. для поиска нужно прочесть с диска в 2 раза меньше данных
если поиск производится редко, а элементы добавляются часто, то проще хранить массив структур, т.к. меньше возни при добавлении
по жизни:
из описанного читается классическая ситуация — кто-то выше хочет найти человека. собеседущюий вас в новом человеке не заинтересован (скорее всего, боится потерять свою позицию), поэтому ищет повод завалить всех кандидатов.
Здравствуйте, omgOnoz, Вы писали:
O>По сути идет оптимизация чтения одного-нескольких полей из базы данных. Это выгодно в тех задачах, когда редко интересен полных набор полей. Интересный подход.
Ага. Для удобства аналитики данные в Hadoop обычно де-нормализованные. 100 полей в одной таблице — обычное дело. Для анализа это удобнее чем нормализованные 30 таблиц по 2-10 полей.
Еще одни аспект вспомнил:
4) Степень архивации — Если данных много и они хранятся блоками, то помещая в блоки части отдельных массивов (часть столбца таблицы) вместо массивов структур (несколько из запесей теблицы) повышается степерь сжатия этих блоков т.к. там данные однотипные. Тот же Parquet умеет сжимать. Некоторые даже в памяти хранят сжатые данные.
Здравствуйте, omgOnoz, Вы писали:
BZ>>вот это и надо было задвинуть. а каких именно тебе данных не хватало?
O>А этот вопрос смысл имеет при подобном отношении?
каком отношении? человек считай не смог ответить сколько будет 2*2. выглядит так что у него просто нет опыта нихкоуровневой оптимизации, а именно это интересовало спрашивающего. для сравнения почитай ответы в треде
Здравствуйте, BulatZiganshin, Вы писали:
BZ>каком отношении? человек считай не смог ответить сколько будет 2*2. выглядит так что у него просто нет опыта нихкоуровневой оптимизации, а именно это интересовало спрашивающего. для сравнения почитай ответы в треде
По мне это вопрос из какой-то методички.
Прикладные задачи, требующие подобных знаний редки. Эти знания специфичны — туже методичку почитай, за день освоишься.
Сейчас вспомнил, что 1 раз сталкивался, но хорошо про неё забыл.
