Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Ускорить код 
V
    Опции темы
Rrader
  Дата 12.5.2008, 12:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Inspired =)
***


Профиль
Группа: Экс. модератор
Сообщений: 1535
Регистрация: 7.5.2005

Репутация: нет
Всего: 191
Здравствуйте! Моим заданием было написать функцию, возвращающую число нулевых битов в символах строки, быстрым методом. Я сделал так:
Код

int CountZeroBits2(const char *s)
{
  int ZBitCnt = 0;
  int i = 0;
  unsigned char B;
  while (s[i] != 0){
    B = (unsigned char)s[i];
    // Инверсия для дальнейшей проверки "нулевых" битов
    B = ~B;
    // Прямой расчёт
    ZBitCnt += ((B & 1) + ((B & 2) >> 1) + ((B & 4) >> 2) + ((B & 8) >> 3) +
      ((B & 16) >> 4) + ((B & 32) >> 5) + ((B & 64) >> 6) + ((B & 128) >> 7));
    i++;
  }
  return ZBitCnt;
}

Но мне сказали, что неоптимально. Как можно улучшить данный код?

Это сообщение отредактировал(а) Rrader - 12.5.2008, 12:41


--------------------
Let's do this quickly!
Rest in peace, Vit!
PM MAIL Skype   Вверх
Rififi
Дата 12.5.2008, 12:45 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1254
Регистрация: 9.3.2008

Репутация: 11
Всего: 36
Rrader, 
Это тебе поможет.
PM MAIL   Вверх
Lazin
Дата 12.5.2008, 12:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
Код

int pop(unsigned x)
{
    unsigned n;
    n = (x >> 1) & 033333333333;        // Подсчет битов
    x = x - n ;                         //в 3-битовых
    n = (n >> 1) & 033333333333;        // полях
    х = х - n;                          //
    х = (х + (х >> 3)) & 030707070707;  // 6-разрядные суммы
    return х % 63;                      // Сложение 6-разрядных сумм
}

Нагло сппрочитано в книге Г. Уоррен - "Алгоритмические трюки для программистов" smile 


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
Alek86
Дата 12.5.2008, 12:59 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1299
Регистрация: 30.1.2007
Где: Киев

Репутация: 21
Всего: 25
можно составить массив байтов(unsigned char), в котором будут 256 элементов
в нем под Х-тым номером будет записано число нудевых бит в числе Х

к примеру:

Код

unsigned char mas_null_bits[256];
mas_null_bits[0] = 8; 0x00 содержит 8 нулевых бит
mas_null_bits[1] = 7; 0x01 содержит 7 нулевых бит
mas_null_bits[2] = 7; 0x00 содержит 7 нулевых бит
//...
mas_null_bits[254] = 1; 0xfe содержит 1 нулевых бит
mas_null_bits[255] = 0; 0xff содержит 0 нулевых бит


а потом пробегаться по твоей строке и суммировать соответсттвующие ей элементы массива:

Код

int CountZeroBits2(const char *s) {
  int count_null_bits = 0;
  while (s) {
    count_null_bits += mas_null_bits[*s];
    ++s;
  }
 return count_null_bits;
}


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

Добавлено через 54 секунды
Lazin, кажется, мое быстрее  smile 


--------------------
user posted image    user posted image
PM MAIL   Вверх
Lazin
Дата 12.5.2008, 13:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
Цитата(Alek86 @  12.5.2008,  12:59 Найти цитируемый пост)
кажется, мое быстрее   smile   

мое сразу в 4х байтах считает, так что это еще надо посмотреть что быстрее smile 


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
Alek86
Дата 12.5.2008, 13:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1299
Регистрация: 30.1.2007
Где: Киев

Репутация: 21
Всего: 25
только на каждой итерации превращать 4 символа в 1 (недолго, но все же) + проверять выход за границы строки (если четверками прыгать, то очень легко)
бррр...

тогда мой код  проще smile


--------------------
user posted image    user posted image
PM MAIL   Вверх
Lazin
Дата 12.5.2008, 13:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
Цитата(Alek86 @  12.5.2008,  13:28 Найти цитируемый пост)
только на каждой итерации превращать 4 символа в 1 (недолго, но все же)

совсем наоборот, что-то вроде 
Код

unsigned* iter = reinterpret_cast<unsigned*>(str);
sum += pop(*iter);
iter++;

и вперед smile
ну и заранее вычислить адрес последнего элемента массива, а все что не кратно 4 - по одному байту... 
просто в моем случае обращений к памяти будет почти(почти, потому-что количество байт строки может не быть кратно 4-м) в 8 раз меньше  smile (4 обращения на каждую итерацию + еще 4 на чтение из mas_null_bits будут дороже чем немного вычислений smile )

Добавлено через 43 секунды
Цитата(Alek86 @  12.5.2008,  13:28 Найти цитируемый пост)
тогда мой код  проще

так и да, проще  smile 


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
Alek86
Дата 12.5.2008, 13:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1299
Регистрация: 30.1.2007
Где: Киев

Репутация: 21
Всего: 25
усе, я завелся smile

если подскажешь как в C++ можно замерить время (типа GetTickCount() - GetTickCount() виндозного), то будем ща меряться (для большой строчки сгенеренной тем же рандомом)


--------------------
user posted image    user posted image
PM MAIL   Вверх
Lazin
Дата 12.5.2008, 14:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
a = GetTickCount();
вычисляем
GetTickCount() - a;



--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
Alek86
Дата 12.5.2008, 14:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1299
Регистрация: 30.1.2007
Где: Киев

Репутация: 21
Всего: 25
Цитата(Lazin @  12.5.2008,  14:03 Найти цитируемый пост)
a = GetTickCount();вычисляемGetTickCount() - a;

smile

Цитата(Alek86 @  12.5.2008,  13:48 Найти цитируемый пост)
типа GetTickCount() - GetTickCount() виндозного


я просто не помню, как и что подключать для этой функции надо

Добавлено @ 14:31
в общем тут 2 кода
можешь покритиковать
если знаешь, как подключить - подскажи, ато никак не проверишь...

Код

#include "stdlib.h"

int Aleks_method(const char* str) {
  std::cout << "Aleks_method" << std::endl;
  unsigned char mas_null_bits[256];
  for (int i = 0; i < 256; ++i)
    mas_null_bits[i] = unsigned char(rand() % 8); // no matter
  std::cout << "Started" << std::endl;
  int count_null_bits = 0;
  while (*str) {
    count_null_bits += mas_null_bits[*reinterpret_cast<const unsigned char*>(str)];
    ++str;
  }
  std::cout << "Finished" << std::endl;
  return count_null_bits;
}

int pop(unsigned x) {
  unsigned n;
  n = (x >> 1) & 033333333333;        // Подсчет битов
  x = x - n ;                         //в 3-битовых
  n = (n >> 1) & 033333333333;        // полях
  x = x - n;                          //
  x = (x + (x >> 3)) & 030707070707;  // 6-разрядные суммы
  return x % 63;                      // Сложение 6-разрядных сумм
}

int Lazins_method(const char* str) {
  std::cout << "Lazins_method" << std::endl;
  std::cout << "Started" << std::endl;
  bool finished = false;
  int sum = 0;
  const unsigned* iter = reinterpret_cast<const unsigned*>(str);
  while (true) {
    char* p_ch = reinterpret_cast<char*>(const_cast<unsigned*>(iter));
    if (!p_ch[0])
      break;
    if (!p_ch[1]) {
      p_ch[2] = p_ch[3] = 0;
      finished = true;
    } else if (!p_ch[2]) {
      p_ch[3] = 0;
      finished = true;
    }
    sum += pop(*iter);
    ++iter;
  }
  std::cout << "Finished" << std::endl;
  return sum;
}


int main() {
  typedef std::vector<char> String;
  std::vector<char> str(1000000);
  for(String::iterator it = str.begin(); it != str.end(); ++it)
    if (char ch = char(rand() % 256))
      *it = ch;
  Aleks_method(&str[0]);
  Lazins_method(&str[0]);
}


Это сообщение отредактировал(а) Alek86 - 12.5.2008, 14:32


--------------------
user posted image    user posted image
PM MAIL   Вверх
math64
Дата 12.5.2008, 15:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72
Я считаю биты так (считаются единичные биты, но легко переделать на нулевые):
Код

int countBits (int n) {
  n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
  n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF);
  n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF);
  return n;
}

Почему работает метод Уоррена пока не понял.

Это сообщение отредактировал(а) math64 - 12.5.2008, 15:01
PM   Вверх
Alek86
Дата 12.5.2008, 15:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1299
Регистрация: 30.1.2007
Где: Киев

Репутация: 21
Всего: 25
в общем такой код
Код

#include "stdlib.h"
#include "windows.h"

int Aleks_method(const char* str) {
  std::cout << "Aleks_method" << std::endl;
  unsigned char mas_null_bits[256];
  for (int i = 0; i < 256; ++i)
    mas_null_bits[i] = unsigned char(rand() % 8); // no matter
  std::cout << "Started" << std::endl;
  DWORD start = GetTickCount();
  int count_null_bits = 0;
  while (*str) {
    count_null_bits += mas_null_bits[*reinterpret_cast<const unsigned char*>(str)];
    ++str;
  }
  DWORD finish = GetTickCount();
  std::cout << "Finished" << std::endl;
  double duration = (double)(finish - start);
  std::cout << "Spent time:" << duration << std::endl;
  return count_null_bits;
}

int pop(unsigned x) {
  unsigned n;
  n = (x >> 1) & 033333333333;        // Подсчет битов
  x = x - n ;                         //в 3-битовых
  n = (n >> 1) & 033333333333;        // полях
  x = x - n;                          //
  x = (x + (x >> 3)) & 030707070707;  // 6-разрядные суммы
  return x % 63;                      // Сложение 6-разрядных сумм
}

int Lazins_method(const char* str) {
  std::cout << "Lazins_method" << std::endl;
  std::cout << "Started" << std::endl;
  DWORD start = GetTickCount();
  bool finished = false;
  int sum = 0;
  const unsigned* iter = reinterpret_cast<const unsigned*>(str);
  while (true) {
    char* p_ch = reinterpret_cast<char*>(const_cast<unsigned*>(iter));
    if (!p_ch[0])
      break;
    if (!p_ch[1]) {
      p_ch[2] = p_ch[3] = 0;
      finished = true;
    } else if (!p_ch[2]) {
      p_ch[3] = 0;
      finished = true;
    }
    sum += pop(*iter);
    ++iter;
    }
  DWORD finish = GetTickCount();
  std::cout << "Finished" << std::endl;
  double duration = (double)(finish - start);
  std::cout << "Spent time:" << duration << std::endl;
  return sum;
}


int main() {
  typedef std::vector<char> String;
  std::vector<char> str(200000000, '2');  // тут можно менять
  Aleks_method(&str[0]);
  Lazins_method(&str[0]);
  system("pause");
}


дает у меня в релизе такой результат (MSVC 2005)
Код

Aleks_method
Started
Finished
Spent time:172
Lazins_method
Started
Finished
Spent time:313
Press any key to continue . . .



--------------------
user posted image    user posted image
PM MAIL   Вверх
Lazin
Дата 12.5.2008, 15:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
у мну вот так

Код

// zerocnt.cpp : Defines the entry point for the console application.
//

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <windows.h>

unsigned char get_z_cnt(unsigned char a)
{
    unsigned char res = 0;
    for (int i = 0; i < 8; ++i)
    {
        res += (a >> i) & 1;
    }
    return res;
}

unsigned get_z_cnt_u(unsigned int x)
{
    unsigned n;
    n = (x >> 1) & 033333333333;        // Подсчет битов
    x = x - n ;                         //в 3-битовых
    n = (n >> 1) & 033333333333;        // полях
    x = x - n;                          //
    x = (x + (x >> 3)) & 030707070707;  // 6-разрядные суммы
    return x % 63;                      // Сложение 6-разрядных сумм
}

unsigned char zeros[0x100];

char* test_data_begin;
char* test_data_end;
long sum1, sum2, time1, time2;

const int test_data_sz = 0xfffffff;

int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "Russian");
    for(int i = 0; i < 0x100; i++)
    {
        zeros[i] = get_z_cnt(i);
    }
    test_data_begin = new char[test_data_sz];
    test_data_end = test_data_begin + test_data_sz;
    std::generate(test_data_begin, test_data_end, &rand);

    {
        DWORD time1_ = GetTickCount();
        long sum = 0;
        char* iter = test_data_begin;
        while(iter != test_data_end)
        {
            sum += zeros[(unsigned char)*iter];
            iter++;
        }
        sum1 = sum;
        time1 = GetTickCount() - time1_;
    }

    {
        DWORD time2_ = GetTickCount();
        long sum = 0;
        unsigned* iter = (unsigned*)test_data_begin;
        unsigned* end = (unsigned*)test_data_end;
        end -= 1;
        while(iter < end)
        {
            sum += get_z_cnt_u(*iter);
            iter++;
        }
        char *citer = (char*)iter;
        while(citer != test_data_end)
        {
            sum += zeros[(unsigned char)*citer];
            citer++;
        }
        sum2 = sum;
        time2 = GetTickCount() - time2_;
    }

    std::cout << "Побайтовый подсчет: " << sum1 << std::endl;    
    std::cout << "Время работы = " << time1 << std::endl;

    std::cout << "Подсчет по 4 байта: " << sum2 << std::endl;    
    std::cout << "Время работы = " << time2 << std::endl;

    return 0;
}




результат:
Код

Microsoft Windows [Version 5.2.3790]
(C) Copyright 1985-2003 Microsoft Corp.

C:\__sandbox__\frustrations\zerocnt\release>zerocnt.exe
Побайтовый подсчет: 1073741824
Время работы = 328
Подсчет по 4 байта: 1073741824
Время работы = 453


 smile

Добавлено @ 15:32
вот с этим кодом
Цитата(math64 @  12.5.2008,  15:01 Найти цитируемый пост)
Код

int countBits (int n) {
  n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
  n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF);
  n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF);
  return n;
}

результат такой:

Код


Побайтовый подсчет: 1073741824
Время работы = 328
Подсчет по 4 байта: 1073741824
Время работы = 406
Press any key to continue . . .



Это сообщение отредактировал(а) Lazin - 12.5.2008, 15:34


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
Alek86
Дата 12.5.2008, 15:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1299
Регистрация: 30.1.2007
Где: Киев

Репутация: 21
Всего: 25
Цитата(Lazin @  12.5.2008,  15:26 Найти цитируемый пост)
у мну вот так

ты немного схалявил smile

по условию дана строка, так что чтобы узнать ее конец, надобно или самому еще раз циклом пробежаться по всей строке (до нуля) или на каждой итерации проверять
а ты, как вижу, считаешь, что указатель на конец известен


--------------------
user posted image    user posted image
PM MAIL   Вверх
math64
Дата 12.5.2008, 15:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72
Цитата(Lazin @  12.5.2008,  15:26 Найти цитируемый пост)
const int test_data_sz = 0xfffffff;

Размер не делится на 4 - подсчитан ещё один байт за данными, но он видимо  был равен 0, иначе результаты бы не сошлись.
Метод Уоррена медленнее вероятно потому, что в нём есть деление.
PM   Вверх
Страницы: (3) Все [1] 2 3 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0611 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.