Дан массив из n n-битных значений. Подсчитать количество единиц

Главная Форумы Программирование Дан массив из n n-битных значений. Подсчитать количество единиц

В этой теме 4 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 мес., 2 нед. назад.

Просмотр 5 сообщений - с 1 по 5 (из 5 всего)
  • Автор
    Сообщения
  • #4264

    ghost
    Участник

    Добрый день!
    Есть такая статья на не безыисвестном сайте.
    Как проходит телефонное собеседование в Google: рассказ из первых рук от кандидата на должность технического директора

    Не могли бы вы описать или дать пример, или ссылку. На то о чем идет речь в вопросе.

    Дан массив из 10000 16-битных значений, каков наиболее эффективный способ подсчитать биты?

    Мой ответ:
    Сдвинуть биты вправо по 64-битным словам — все по заветам Кернигана.
    Рекрутер:
    Нет.
    Я:
    Есть и более быстрые способы обработки 64-битных слов с применением масок, но по телефону я объяснить их не смогу, нужно писать код.
    Рекрутер:
    Верный ответ — использовать таблицу соответствий и просуммировать результаты.
    Я:
    Это на каком виде CPU? А давайте проведем бенчмарки вашего и моего кода?
    Рекрутер:
    Это не входит в задачи теста.
    Я:
    А что в них входит?
    Рекрутер:
    Проверить, насколько хорошо вы знаете правильные ответы.

    Долго еще будет продолжаться этот бред? Поиск по 8-битной таблице соответствий будет обрабатывать байты один за другим, а вот метод 64-битных масок будет обрабатывать 8-байтовые слова одновременно (а современные процессоры даже смогут обрабатывать 128-битные слова с десятикратным приростом скорости). Поиск по 64-битной таблице соответствий пока что находится за гранью способностей современных компьютеров — так что сразу понятно, что будет быстрее.

    #4265

    ghost
    Участник

    16 бит — 0101 0101 0101 0101
    Я так понимаю, надо узнать количество единиц. В примере 8 единиц.

    #4267

    По статье (я ее просмотрел). Есть стойкое ощущение, что парня сильно умыли на собеседовании в google, чтобы поднять ЧСВ он решил «отомстить» и слегка наврать. Последний вопрос я не понял (возможно, в силу некомпетентности автор статьи даже смысл не смог передать).

    По вопросу:

    Я так понимаю, надо узнать количество единиц. В примере 8 единиц.

    Если так — то самый быстрый способ — это завести таблицу, в которой для каждого числа (допустим 8-ми разрядного) записать число единиц. Т.е. банально в массив помещаем количества единиц. Нужно узнать сколько единиц в числе 123 — обращаемся в table[123]. Расчет такой таблицы можно сделать весьма быстро. Чтобы посчитать число единиц во всей последовательности (1000 чисел) пишем что-то типа:

    for (int i = 0; i < 10000/sizeof(table[0]); ++i) {
      count += table[seq[i]];
    }

    Это схематично. Асимптотическая сложность такого алгоритма — O(n/m) где n — длина исходной последовательности, а m — разрядность чисел в таблице. Лично мне очевидно, что более эффективного решения нет, если кто-то знает такой способ — очень прошу объяснить.

    По ответу и сдвигам. Я не понял что там предлагается и как это связано с вопросом (возможно ты неверно понял вопрос, как и я). Сдвиги тут никак не помогут. Берем число 0101. В нем 2 единицы, куда его сдвинуть чтобы получить нужный мне ответ? У числа 1100 и 0011 тоже две единицы. Сдвигами одно число в другое не превращается.

    #4268

    ghost
    Участник

    В общем нашел я статью на habre, в зарубежных источниках тоже много про это написано.
    Я так понимаю тут идет речь о:

    подсчёт единичных битов в переменных размером от 8 до 64 битов.

    Помню у Яндекса тоже задачи такие были. Очень полезная задача, помогает разобраться в битовых операциях.
    Ну и код для демонстрации:

    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>
    
    typedef unsigned char      u8;
    typedef unsigned int       u32;
    
    u8 CountOnes0 (u8 n) {
      u8 res = 0;
      while (n) {
        res += n&1;
        n >>= 1;
      }
      return res;
    }
    
    int main()
    {
        u32 i=0,sum=0;
        u32 m=0;
        long n=UINT_MAX;//перебираем 2**32 элемента
        for (i=0;i<n;i++){
            u8 k = m & 0xFF;//значение не должно быть больше 256
            sum += CountOnes0(k);
            m= ( 19993 * m + 1 );
        }
        printf("sum:%u",sum);
        return 0;
    }
    

    #4272

    Это вообще что?
    Ну вот смотри, у тебя есть байт, ты назвал его u8:
    typedef unsigned char u8;
    Тебе надо посчитать сколько в нем единиц. Ты для этого выполнишь в худшем случае 8 операций сдвига, 8 операций логического И, 8 проверок n на равенство нулю и 8 суммирований. Это только то, что внутри функции CountOnes0 записано. Вне этой функции добавляется еще одно логическое И, суммирование, умножение и сложение. Я не учитываю затраты на вызов функции, пускай она проинлайнится.

    Что предложил я (возможно такой же вариант предложили в google) — table[seq[i]], операция обращения к элементу массива — это одно умножение и одно сложение (к адресу начала массива прибавляется i*sizeof(Type)). Да, одно из них можно убрать, кстати. Интересно, что же работает быстрее?

    ЗЫ. В твоем коде вообще не все понял. Как этот код с задачей связан (ну кроме функции, которая каким-то стремным способом считает число единиц)? — в задаче ведь есть массив из 10 тысяч значений, а у тебя этот массив где? — ты считаешь количества единиц для некоторых k, которые получаешь из m, выковыривая последние 8 разрядов оттуда. Сами эти m при этой считаешь по какой-то дикой формуле. Просто не понятно как это с исходной задачей связано, но если ты доработаешь это (чтобы условию соответствовало) — можно будет скорость сравнить (предполагаю, что мой вариант будет работать раз в 5-10 быстрее).

Просмотр 5 сообщений - с 1 по 5 (из 5 всего)

Для ответа в этой теме необходимо авторизоваться.