VPF::Ускорить код - Форум программистов

Lazin

Дата 12.5.2008, 15:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

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

Цитата(Alek86 @ 12.5.2008, 15:39

)

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

есть немного, но у меня есть отмазка, я заполнял rand-ом, поэтому там 0 мог где угодно встретиться

Цитата(math64 @ 12.5.2008, 15:44

)

Размер не делится на 4 - подсчитан ещё один байт за данными, но он видимо был равен 0, иначе результаты бы не сошлись.

я там потом считаю, то что не кратно 4

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Alek86

Дата 12.5.2008, 16:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 21
Всего: 25

халявщик...

Код

for (int i = 0; i < test_data_sz; ++i)
  if (!test_data_begin[i]) test_data_begin[i] = 1;
test_data_begin[i - 1] = 0;

ладно, в общем автору темы вон сколько вариантов - и все как на подбор шустрые

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

--------------------

Rrader

Дата 12.5.2008, 18:25 (ссылка)

(нет голосов)

Загрузка ...

Inspired =)

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

Репутация: нет
Всего: 191

Всем спасибо! smile

--------------------

Let's do this quickly!
Rest in peace, Vit!

SABROG

Дата 12.5.2008, 18:44 (ссылка)

(нет голосов)

Загрузка ...

Hacker

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

Репутация: 4
Всего: 91

О кстати:

Код


/*
 * Copyright (c) 2003, 2007 Matteo Frigo
 * Copyright (c) 2003, 2007 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */


/* machine-dependent cycle counters code. Needs to be inlined. */

/***************************************************************************/
/* To use the cycle counters in your code, simply #include "cycle.h" (this
   file), and then use the functions/macros:

                 ticks getticks(void);

   ticks is an opaque typedef defined below, representing the current time.
   You extract the elapsed time between two calls to gettick() via:

                 double elapsed(ticks t1, ticks t0);

   which returns a double-precision variable in arbitrary units.  You
   are not expected to convert this into human units like seconds; it
   is intended only for *comparisons* of time intervals.

   (In order to use some of the OS-dependent timer routines like
   Solaris' gethrtime, you need to paste the autoconf snippet below
   into your configure.ac file and #include "config.h" before cycle.h,
   or define the relevant macros manually if you are not using autoconf.)
*/

/***************************************************************************/
/* This file uses macros like HAVE_GETHRTIME that are assumed to be
   defined according to whether the corresponding function/type/header
   is available on your system.  The necessary macros are most
   conveniently defined if you are using GNU autoconf, via the tests:
   
   dnl ---------------------------------------------------------------------

   AC_C_INLINE
   AC_HEADER_TIME
   AC_CHECK_HEADERS([sys/time.h c_asm.h intrinsics.h mach/mach_time.h])

   AC_CHECK_TYPE([hrtime_t],[AC_DEFINE(HAVE_HRTIME_T, 1, [Define to 1 if hrtime_t is defined in <sys/time.h>])],,[#if HAVE_SYS_TIME_H
#include <sys/time.h>
#endif])

   AC_CHECK_FUNCS([gethrtime read_real_time time_base_to_time clock_gettime mach_absolute_time])

   dnl Cray UNICOS _rtc() (real-time clock) intrinsic
   AC_MSG_CHECKING([for _rtc intrinsic])
   rtc_ok=yes
   AC_TRY_LINK([#ifdef HAVE_INTRINSICS_H
#include <intrinsics.h>
#endif], [_rtc()], [AC_DEFINE(HAVE__RTC,1,[Define if you have the UNICOS _rtc() intrinsic.])], [rtc_ok=no])
   AC_MSG_RESULT($rtc_ok)

   dnl ---------------------------------------------------------------------
*/

/***************************************************************************/

#if TIME_WITH_SYS_TIME
# include <sys/time.h>
# include <time.h>
#else
# if HAVE_SYS_TIME_H
#  include <sys/time.h>
# else
#  include <time.h>
# endif
#endif

#define INLINE_ELAPSED(INL) static INL double elapsed(ticks t1, ticks t0) \
{                                      \
     return (double)t1 - (double)t0;                      \
}

/*----------------------------------------------------------------*/
/* Solaris */
#if defined(HAVE_GETHRTIME) && defined(HAVE_HRTIME_T) && !defined(HAVE_TICK_COUNTER)
typedef hrtime_t ticks;

#define getticks gethrtime

INLINE_ELAPSED(inline)

#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
/* AIX v. 4+ routines to read the real-time clock or time-base register */
#if defined(HAVE_READ_REAL_TIME) && defined(HAVE_TIME_BASE_TO_TIME) && !defined(HAVE_TICK_COUNTER)
typedef timebasestruct_t ticks;

static __inline ticks getticks(void)
{
     ticks t;
     read_real_time(&t, TIMEBASE_SZ);
     return t;
}

static __inline double elapsed(ticks t1, ticks t0) /* time in nanoseconds */
{
     time_base_to_time(&t1, TIMEBASE_SZ);
     time_base_to_time(&t0, TIMEBASE_SZ);
     return (((double)t1.tb_high - (double)t0.tb_high) * 1.0e9 + 
         ((double)t1.tb_low - (double)t0.tb_low));
}

#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
/*
 * PowerPC ``cycle'' counter using the time base register.
 */
#if ((((defined(__GNUC__) && (defined(__powerpc__) || defined(__ppc__))) || (defined(__MWERKS__) && defined(macintosh)))) || (defined(__IBM_GCC_ASM) && (defined(__powerpc__) || defined(__ppc__))))  && !defined(HAVE_TICK_COUNTER)
typedef unsigned long long ticks;

static __inline__ ticks getticks(void)
{
     unsigned int tbl, tbu0, tbu1;

     do {
      __asm__ __volatile__ ("mftbu %0" : "=r"(tbu0));
      __asm__ __volatile__ ("mftb %0" : "=r"(tbl));
      __asm__ __volatile__ ("mftbu %0" : "=r"(tbu1));
     } while (tbu0 != tbu1);

     return (((unsigned long long)tbu0) << 32) | tbl;
}

INLINE_ELAPSED(__inline__)

#define HAVE_TICK_COUNTER
#endif

/* MacOS/Mach (Darwin) time-base register interface (unlike UpTime,
   from Carbon, requires no additional libraries to be linked). */
#if defined(HAVE_MACH_ABSOLUTE_TIME) && defined(HAVE_MACH_MACH_TIME_H) && !defined(HAVE_TICK_COUNTER)
#include <mach/mach_time.h>
typedef uint64_t ticks;
#define getticks mach_absolute_time
INLINE_ELAPSED(__inline__)
#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
/*
 * Pentium cycle counter 
 */
#if (defined(__GNUC__) || defined(__ICC)) && defined(__i386__)  && !defined(HAVE_TICK_COUNTER)
typedef unsigned long long ticks;

static __inline__ ticks getticks(void)
{
     ticks ret;

     __asm__ __volatile__("rdtsc": "=A" (ret));
     /* no input, nothing else clobbered */
     return ret;
}

INLINE_ELAPSED(__inline__)

#define HAVE_TICK_COUNTER
#define TIME_MIN 5000.0   /* unreliable pentium IV cycle counter */
#endif

/* Visual C++ -- thanks to Morten Nissov for his help with this */
#if _MSC_VER >= 1200 && _M_IX86 >= 500 && !defined(HAVE_TICK_COUNTER)
#include <windows.h>
typedef LARGE_INTEGER ticks;
#define RDTSC __asm __emit 0fh __asm __emit 031h /* hack for VC++ 5.0 */

static __inline ticks getticks(void)
{
     ticks retval;

     __asm {
      RDTSC
      mov retval.HighPart, edx
      mov retval.LowPart, eax
     }
     return retval;
}

static __inline double elapsed(ticks t1, ticks t0)
{  
     return (double)t1.QuadPart - (double)t0.QuadPart;
}  

#define HAVE_TICK_COUNTER
#define TIME_MIN 5000.0   /* unreliable pentium IV cycle counter */
#endif

/*----------------------------------------------------------------*/
/*
 * X86-64 cycle counter
 */
#if (defined(__GNUC__) || defined(__ICC) || defined(__SUNPRO_C)) && defined(__x86_64__)  && !defined(HAVE_TICK_COUNTER)
typedef unsigned long long ticks;

static __inline__ ticks getticks(void)
{
     unsigned a, d; 
     asm volatile("rdtsc" : "=a" (a), "=d" (d)); 
     return ((ticks)a) | (((ticks)d) << 32); 
}

INLINE_ELAPSED(__inline__)

#define HAVE_TICK_COUNTER
#endif

/* PGI compiler, courtesy Cristiano Calonaci, Andrea Tarsi, & Roberto Gori.
   NOTE: this code will fail to link unless you use the -Masmkeyword compiler
   option (grrr). */
#if defined(__PGI) && defined(__x86_64__) && !defined(HAVE_TICK_COUNTER) 
typedef unsigned long long ticks;
static ticks getticks(void)
{
    asm(" rdtsc; shl    $0x20,%rdx; mov    %eax,%eax; or     %rdx,%rax;    ");
}
INLINE_ELAPSED(__inline__)
#define HAVE_TICK_COUNTER
#endif

/* Visual C++, courtesy of Dirk Michaelis */
#if _MSC_VER >= 1400 && (defined(_M_AMD64) || defined(_M_X64)) && !defined(HAVE_TICK_COUNTER)

#include <intrin.h>
#pragma intrinsic(__rdtsc)
typedef unsigned __int64 ticks;
#define getticks __rdtsc
INLINE_ELAPSED(__inline)

#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
/*
 * IA64 cycle counter
 */

/* intel's icc/ecc compiler */
#if (defined(__EDG_VERSION) || defined(__ECC)) && defined(__ia64__) && !defined(HAVE_TICK_COUNTER)
typedef unsigned long ticks;
#include <ia64intrin.h>

static __inline__ ticks getticks(void)
{
     return __getReg(_IA64_REG_AR_ITC);
}
 
INLINE_ELAPSED(__inline__)
 
#define HAVE_TICK_COUNTER
#endif

/* gcc */
#if defined(__GNUC__) && defined(__ia64__) && !defined(HAVE_TICK_COUNTER)
typedef unsigned long ticks;

static __inline__ ticks getticks(void)
{
     ticks ret;

     __asm__ __volatile__ ("mov %0=ar.itc" : "=r"(ret));
     return ret;
}

INLINE_ELAPSED(__inline__)

#define HAVE_TICK_COUNTER
#endif

/* HP/UX IA64 compiler, courtesy Teresa L. Johnson: */
#if defined(__hpux) && defined(__ia64) && !defined(HAVE_TICK_COUNTER)
#include <machine/sys/inline.h>
typedef unsigned long ticks;

static inline ticks getticks(void)
{
     ticks ret;

     ret = _Asm_mov_from_ar (_AREG_ITC);
     return ret;
}

INLINE_ELAPSED(inline)

#define HAVE_TICK_COUNTER
#endif

/* Microsoft Visual C++ */
#if defined(_MSC_VER) && defined(_M_IA64) && !defined(HAVE_TICK_COUNTER)
typedef unsigned __int64 ticks;

#  ifdef __cplusplus
extern "C"
#  endif
ticks __getReg(int whichReg);
#pragma intrinsic(__getReg)

static __inline ticks getticks(void)
{
     volatile ticks temp;
     temp = __getReg(3116);
     return temp;
}

INLINE_ELAPSED(inline)

#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
/*
 * PA-RISC cycle counter 
 */
#if defined(__hppa__) || defined(__hppa) && !defined(HAVE_TICK_COUNTER)
typedef unsigned long ticks;

#  ifdef __GNUC__
static __inline__ ticks getticks(void)
{
     ticks ret;

     __asm__ __volatile__("mfctl 16, %0": "=r" (ret));
     /* no input, nothing else clobbered */
     return ret;
}
#  else
#  include <machine/inline.h>
static inline unsigned long getticks(void)
{
     register ticks ret;
     _MFCTL(16, ret);
     return ret;
}
#  endif

INLINE_ELAPSED(inline)

#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
/* S390, courtesy of James Treacy */
#if defined(__GNUC__) && defined(__s390__) && !defined(HAVE_TICK_COUNTER)
typedef unsigned long long ticks;

static __inline__ ticks getticks(void)
{
     ticks cycles;
     __asm__("stck 0(%0)" : : "a" (&(cycles)) : "memory", "cc");
     return cycles;
}

INLINE_ELAPSED(__inline__)

#define HAVE_TICK_COUNTER
#endif
/*----------------------------------------------------------------*/
#if defined(__GNUC__) && defined(__alpha__) && !defined(HAVE_TICK_COUNTER)
/*
 * The 32-bit cycle counter on alpha overflows pretty quickly, 
 * unfortunately.  A 1GHz machine overflows in 4 seconds.
 */
typedef unsigned int ticks;

static __inline__ ticks getticks(void)
{
     unsigned long cc;
     __asm__ __volatile__ ("rpcc %0" : "=r"(cc));
     return (cc & 0xFFFFFFFF);
}

INLINE_ELAPSED(__inline__)

#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
#if defined(__GNUC__) && defined(__sparc_v9__) && !defined(HAVE_TICK_COUNTER)
typedef unsigned long ticks;

static __inline__ ticks getticks(void)
{
     ticks ret;
     __asm__ __volatile__("rd %%tick, %0" : "=r" (ret));
     return ret;
}

INLINE_ELAPSED(__inline__)

#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
#if (defined(__DECC) || defined(__DECCXX)) && defined(__alpha) && defined(HAVE_C_ASM_H) && !defined(HAVE_TICK_COUNTER)
#  include <c_asm.h>
typedef unsigned int ticks;

static __inline ticks getticks(void)
{
     unsigned long cc;
     cc = asm("rpcc %v0");
     return (cc & 0xFFFFFFFF);
}

INLINE_ELAPSED(__inline)

#define HAVE_TICK_COUNTER
#endif
/*----------------------------------------------------------------*/
/* SGI/Irix */
#if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_SGI_CYCLE) && !defined(HAVE_TICK_COUNTER)
typedef struct timespec ticks;

static inline ticks getticks(void)
{
     struct timespec t;
     clock_gettime(CLOCK_SGI_CYCLE, &t);
     return t;
}

static inline double elapsed(ticks t1, ticks t0)
{
     return ((double)t1.tv_sec - (double)t0.tv_sec) * 1.0E9 +
      ((double)t1.tv_nsec - (double)t0.tv_nsec);
}
#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
/* Cray UNICOS _rtc() intrinsic function */
#if defined(HAVE__RTC) && !defined(HAVE_TICK_COUNTER)
#ifdef HAVE_INTRINSICS_H
#  include <intrinsics.h>
#endif

typedef long long ticks;

#define getticks _rtc

INLINE_ELAPSED(inline)

#define HAVE_TICK_COUNTER
#endif

/*----------------------------------------------------------------*/
/* MIPS ZBus */
#if HAVE_MIPS_ZBUS_TIMER
#if defined(__mips__) && !defined(HAVE_TICK_COUNTER)
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>

typedef uint64_t ticks;

static inline ticks getticks(void)
{
  static uint64_t* addr = 0;

  if (addr == 0)
  {
    uint32_t rq_addr = 0x10030000;
    int fd;
    int pgsize;

    pgsize = getpagesize();
    fd = open ("/dev/mem", O_RDONLY | O_SYNC, 0);
    if (fd < 0) {
      perror("open");
      return NULL;
    }
    addr = mmap(0, pgsize, PROT_READ, MAP_SHARED, fd, rq_addr);
    close(fd);
    if (addr == (uint64_t *)-1) {
      perror("mmap");
      return NULL;
    }
  }

  return *addr;
}

INLINE_ELAPSED(inline)

#define HAVE_TICK_COUNTER
#endif
#endif /* HAVE_MIPS_ZBUS_TIMER */

Это сообщение отредактировал(а) SABROG - 12.5.2008, 18:57

--------------------

Национальная группа Russian Federation на QtCentre.

Mayk

Дата 18.6.2008, 07:26 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

Цитата(Rififi @ 12.5.2008, 16:45

)

Rrader,
Это тебе поможет.

Ну вообщем кажется оттуда уже всё перебрали smile

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

SABROG

Дата 18.6.2008, 08:53 (ссылка)

(нет голосов)

Загрузка ...

Hacker

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

Репутация: 4
Всего: 91

Метод с массивом я бы назвал отмазкой, т.к. сначала человек сам вычисляет количество бит для каждого байта в диапозоне 0-255, после чего тупо выводит их с помощью программы, если бы не дополнительное условие о том, что надо для строк переменной длинны вести подсчет smile

Кстати, а нужен ли индекс i ? Может применить адресную арифметику и увеличивать сам указатель ?
Кроме того, если мы берем строку, то нулевой индекс нам не нужен вообще, т.к. 0 это конец строки. А еще диапозон значений можно сократить до рамок 32-241.

Это сообщение отредактировал(а) SABROG - 18.6.2008, 09:11

--------------------

Национальная группа Russian Federation на QtCentre.

Alek86

Дата 18.6.2008, 09:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 21
Всего: 25

Цитата(SABROG @ 18.6.2008, 08:53

)

Метод с массивом я бы назвал отмазкой

ничего себе отмазка!
ты на олимпиадах бывал по программированию? там такие "отмазки" больше всего баллов и получают

Цитата(SABROG @ 18.6.2008, 08:53

)

сначала человек сам вычисляет количество бит для каждого байта в диапозоне 0-255, после чего тупо

тупо или не тупо - второй вопрос
главное быстро

не хочешь сам свитать колво бит, напиши метапрограмму, кто мешает?

--------------------

SABROG

Дата 18.6.2008, 13:12 (ссылка)

(нет голосов)

Загрузка ...

Hacker

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

Репутация: 4
Всего: 91

Ну вот с применением метапрограммирования получилась такая штука. Выглядит коряво и не оптимизированно, с удовольствием посмотрю на другие варианты.

Код


    template<unsigned n>
    struct NBits
    {
      enum { value = n & 1 ?  NBits<(n >> 1)>::value + 1 : NBits<(n >> 1)>::value};
    };

    template<>
    struct NBits<0>
    {
      enum { value = 0 };
    };

const unsigned char zbits[256] = {
        8-NBits<0>::value, 8-NBits<1>::value, 8-NBits<2>::value, 8-NBits<3>::value, 
        8-NBits<4>::value, 8-NBits<5>::value, 8-NBits<6>::value, 8-NBits<7>::value, 
        8-NBits<8>::value, 8-NBits<9>::value, 8-NBits<10>::value, 8-NBits<11>::value, 
        8-NBits<12>::value, 8-NBits<13>::value, 8-NBits<14>::value, 8-NBits<15>::value, 
        8-NBits<16>::value, 8-NBits<17>::value, 8-NBits<18>::value, 8-NBits<19>::value, 
        8-NBits<20>::value, 8-NBits<21>::value, 8-NBits<22>::value, 8-NBits<23>::value, 
        8-NBits<24>::value, 8-NBits<25>::value, 8-NBits<26>::value, 8-NBits<27>::value, 
        8-NBits<28>::value, 8-NBits<29>::value, 8-NBits<30>::value, 8-NBits<31>::value, 
        8-NBits<32>::value, 8-NBits<33>::value, 8-NBits<34>::value, 8-NBits<35>::value, 
        8-NBits<36>::value, 8-NBits<37>::value, 8-NBits<38>::value, 8-NBits<39>::value, 
        8-NBits<40>::value, 8-NBits<41>::value, 8-NBits<42>::value, 8-NBits<43>::value, 
        8-NBits<44>::value, 8-NBits<45>::value, 8-NBits<46>::value, 8-NBits<47>::value, 
        8-NBits<48>::value, 8-NBits<49>::value, 8-NBits<50>::value, 8-NBits<51>::value, 
        8-NBits<52>::value, 8-NBits<53>::value, 8-NBits<54>::value, 8-NBits<55>::value, 
        8-NBits<56>::value, 8-NBits<57>::value, 8-NBits<58>::value, 8-NBits<59>::value, 
        8-NBits<60>::value, 8-NBits<61>::value, 8-NBits<62>::value, 8-NBits<63>::value, 
        8-NBits<64>::value, 8-NBits<65>::value, 8-NBits<66>::value, 8-NBits<67>::value, 
        8-NBits<68>::value, 8-NBits<69>::value, 8-NBits<70>::value, 8-NBits<71>::value, 
        8-NBits<72>::value, 8-NBits<73>::value, 8-NBits<74>::value, 8-NBits<75>::value, 
        8-NBits<76>::value, 8-NBits<77>::value, 8-NBits<78>::value, 8-NBits<79>::value, 
        8-NBits<80>::value, 8-NBits<81>::value, 8-NBits<82>::value, 8-NBits<83>::value, 
        8-NBits<84>::value, 8-NBits<85>::value, 8-NBits<86>::value, 8-NBits<87>::value, 
        8-NBits<88>::value, 8-NBits<89>::value, 8-NBits<90>::value, 8-NBits<91>::value, 
        8-NBits<92>::value, 8-NBits<93>::value, 8-NBits<94>::value, 8-NBits<95>::value, 
        8-NBits<96>::value, 8-NBits<97>::value, 8-NBits<98>::value, 8-NBits<99>::value, 
        8-NBits<100>::value, 8-NBits<101>::value, 8-NBits<102>::value, 8-NBits<103>::value, 
        8-NBits<104>::value, 8-NBits<105>::value, 8-NBits<106>::value, 8-NBits<107>::value, 
        8-NBits<108>::value, 8-NBits<109>::value, 8-NBits<110>::value, 8-NBits<111>::value, 
        8-NBits<112>::value, 8-NBits<113>::value, 8-NBits<114>::value, 8-NBits<115>::value, 
        8-NBits<116>::value, 8-NBits<117>::value, 8-NBits<118>::value, 8-NBits<119>::value, 
        8-NBits<120>::value, 8-NBits<121>::value, 8-NBits<122>::value, 8-NBits<123>::value, 
        8-NBits<124>::value, 8-NBits<125>::value, 8-NBits<126>::value, 8-NBits<127>::value, 
        8-NBits<128>::value, 8-NBits<129>::value, 8-NBits<130>::value, 8-NBits<131>::value, 
        8-NBits<132>::value, 8-NBits<133>::value, 8-NBits<134>::value, 8-NBits<135>::value, 
        8-NBits<136>::value, 8-NBits<137>::value, 8-NBits<138>::value, 8-NBits<139>::value, 
        8-NBits<140>::value, 8-NBits<141>::value, 8-NBits<142>::value, 8-NBits<143>::value, 
        8-NBits<144>::value, 8-NBits<145>::value, 8-NBits<146>::value, 8-NBits<147>::value, 
        8-NBits<148>::value, 8-NBits<149>::value, 8-NBits<150>::value, 8-NBits<151>::value, 
        8-NBits<152>::value, 8-NBits<153>::value, 8-NBits<154>::value, 8-NBits<155>::value, 
        8-NBits<156>::value, 8-NBits<157>::value, 8-NBits<158>::value, 8-NBits<159>::value, 
        8-NBits<160>::value, 8-NBits<161>::value, 8-NBits<162>::value, 8-NBits<163>::value, 
        8-NBits<164>::value, 8-NBits<165>::value, 8-NBits<166>::value, 8-NBits<167>::value, 
        8-NBits<168>::value, 8-NBits<169>::value, 8-NBits<170>::value, 8-NBits<171>::value, 
        8-NBits<172>::value, 8-NBits<173>::value, 8-NBits<174>::value, 8-NBits<175>::value, 
        8-NBits<176>::value, 8-NBits<177>::value, 8-NBits<178>::value, 8-NBits<179>::value, 
        8-NBits<180>::value, 8-NBits<181>::value, 8-NBits<182>::value, 8-NBits<183>::value, 
        8-NBits<184>::value, 8-NBits<185>::value, 8-NBits<186>::value, 8-NBits<187>::value, 
        8-NBits<188>::value, 8-NBits<189>::value, 8-NBits<190>::value, 8-NBits<191>::value, 
        8-NBits<192>::value, 8-NBits<193>::value, 8-NBits<194>::value, 8-NBits<195>::value, 
        8-NBits<196>::value, 8-NBits<197>::value, 8-NBits<198>::value, 8-NBits<199>::value, 
        8-NBits<200>::value, 8-NBits<201>::value, 8-NBits<202>::value, 8-NBits<203>::value, 
        8-NBits<204>::value, 8-NBits<205>::value, 8-NBits<206>::value, 8-NBits<207>::value, 
        8-NBits<208>::value, 8-NBits<209>::value, 8-NBits<210>::value, 8-NBits<211>::value, 
        8-NBits<212>::value, 8-NBits<213>::value, 8-NBits<214>::value, 8-NBits<215>::value, 
        8-NBits<216>::value, 8-NBits<217>::value, 8-NBits<218>::value, 8-NBits<219>::value, 
        8-NBits<220>::value, 8-NBits<221>::value, 8-NBits<222>::value, 8-NBits<223>::value, 
        8-NBits<224>::value, 8-NBits<225>::value, 8-NBits<226>::value, 8-NBits<227>::value, 
        8-NBits<228>::value, 8-NBits<229>::value, 8-NBits<230>::value, 8-NBits<231>::value, 
        8-NBits<232>::value, 8-NBits<233>::value, 8-NBits<234>::value, 8-NBits<235>::value, 
        8-NBits<236>::value, 8-NBits<237>::value, 8-NBits<238>::value, 8-NBits<239>::value, 
        8-NBits<240>::value, 8-NBits<241>::value, 8-NBits<242>::value, 8-NBits<243>::value, 
        8-NBits<244>::value, 8-NBits<245>::value, 8-NBits<246>::value, 8-NBits<247>::value, 
        8-NBits<248>::value, 8-NBits<249>::value, 8-NBits<250>::value, 8-NBits<251>::value, 
        8-NBits<252>::value, 8-NBits<253>::value, 8-NBits<254>::value, 8-NBits<255>::value             
};

Фишка с рекурсией шаблона была стырена отсюда http://www.rsdn.ru/?summary/560.xml, т.ч. это не моя задумка.

Препроцессор вычисляет количество нулевых битов в каждом из 256 байтов.

--------------------

Национальная группа Russian Federation на QtCentre.

Mayk

Дата 18.6.2008, 13:24 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

Цитата(SABROG @ 18.6.2008, 12:53

)

т.к. сначала человек сам вычисляет количество бит

Так делает только совсем безмозглый человек. Подобные мехаические операции лучше поручить делать питону/руби/кому угодно, которые находят ответ как угодно.

Цитата(SABROG @ 18.6.2008, 17:12

)

делаем кодогенератор

Код


print "int bitCount[] = {"

def splitToBits(int):
    list = [ 0 for i in xrange(8) ]
    count = 0
    for i in xrange(8):
        if int & 1 != 0:
                list[7-i] = 1
                count += 1
        int = int / 2                
    return (list, count)


for i in xrange(256):
    (list,count)=splitToBits(i);
    print "/*%d*/"%i,
    print "%d"%count,
    print "/*%s*/"%list,
    if i != 255:
        print ","
    else:
        print 
print "};"

и получаем готовый код.

Код


int bitCount[] = {
/*0*/ 0 /*[0, 0, 0, 0, 0, 0, 0, 0]*/ ,
/*1*/ 1 /*[0, 0, 0, 0, 0, 0, 0, 1]*/ ,
/*2*/ 1 /*[0, 0, 0, 0, 0, 0, 1, 0]*/ ,
/*3*/ 2 /*[0, 0, 0, 0, 0, 0, 1, 1]*/ ,
/*4*/ 1 /*[0, 0, 0, 0, 0, 1, 0, 0]*/ ,
...
}

Это сообщение отредактировал(а) Mayk - 18.6.2008, 13:25

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Lazin

Дата 18.6.2008, 13:59 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

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

Код


#include <iostream>

template<unsigned n> struct NBits 
{
    enum {value = n & 1 ? NBits<(n >> 1)>::value + 1 : NBits<(n >> 1)>::value};
};

template<> struct NBits<0> 
{
    enum {value = 0};
};

template <int index, int last> struct generator
{
    void operator () (char* data)
    {
        data[index] = NBits<index>::value;
        generator<index+1, last> next;
        next(data);
    }
};

template<int value> struct generator<value, value>
{
    void operator () (char* data)
    {
        //blank...
    }
};

template<int size>
struct bit_cnt_array_init
{
    bit_cnt_array_init(char* data)
    {
        generator<0, size> gen;
        gen(data);
    }
};


char data[256];
bit_cnt_array_init<256> data_init(data);

int main()
{
    for (int i = 0; i < 256; i++)
    {
        std::cout << (int)data[i] << std::endl;
    }
    system("pause");
    return 0;
}

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

Добавлено через 5 минут и 22 секунды
Mayk, а как это, или что-то подобное, можно прикрутить к своей системе сборки? так что-бы если файл изменился, оно код заново нагенерило-бы...

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

Alek86

Дата 18.6.2008, 14:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 21
Всего: 25

Цитата(Lazin @ 18.6.2008, 13:59

)

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

компилер не обязан
но оптимизатор может попробовать

--------------------

SABROG

Дата 18.6.2008, 14:26 (ссылка)

(нет голосов)

Загрузка ...

Hacker

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

Репутация: 4
Всего: 91

Lazin, нехотит на этапе компиляции заполнять. Смотрел отладчиком, заполняет bss секцию во время выполнения. Оптимизация -O2

--------------------

Национальная группа Russian Federation на QtCentre.

Alek86

Дата 18.6.2008, 14:34 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 21
Всего: 25

Цитата(SABROG @ 18.6.2008, 14:26

)

нехотит на этапе компиляции заполнять.

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

--------------------

SABROG

Дата 18.6.2008, 14:41 (ссылка)

(нет голосов)

Загрузка ...

Hacker

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

Репутация: 4
Всего: 91

Мы же вроде сейчас о скорости говорим. А сложность уже достаточно высокая smile

Сейчас задача стоит таким образом:
- компилятор мы заставили вычислять количество бит
- программу заставили использовать эти данные при подсчете количество бит в строке, что увеличило скорость (или нет ?)
- остался вопрос об автозаполнении массива на этапе компиляции, чтобы не приходилось ручками вбивать 0, 1, 2 и т.д.

--------------------

Национальная группа Russian Federation на QtCentre.

Alek86

Дата 18.6.2008, 14:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 21
Всего: 25

Цитата(SABROG @ 18.6.2008, 14:41

)

Мы же вроде сейчас о скорости говорим.

сложность (?) алгоритма (то есть "О большое для количества элементов") - это и есть главный критерий скорости

а то, что ты хочешь сделать - лишние брыкания

Цитата(SABROG @ 18.6.2008, 14:41

)

остался вопрос об автозаполнении массива на этапе компиляции, чтобы не приходилось ручками вбивать 0, 1, 2 и т.д.

скорее всего на C++ это невозможно

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »