Question

Скажем, у меня есть такой байт: 00010001 (с включенными 2 битами)

И я хочу сравнить его с этими байтами: {0000 0110, 0000 0011, 0011 0000, 0000 1100}

Идея состоит в том, чтобы получить байты, которые не совпадают; где (byteA & byteX) == 0 Для примера я должен получить / найти: {0000 0110, 0000 1100}

Это может быть легко, если мы напишем код, в котором мы зациклим массив байтов. Вот пример:

byte seek = 17;
byte[] pool = {6, 3, 48, 12 };
for(int p=0; p<pool.Length; p++)
{
    if((pool[p] & seek)==0)
    {
        //Usefull
    }
}

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

for(int p1=0; p1<pool.Length; p1++)
{
    for(int p2=0; p2<pool.Length; p1++)
    {
        if((pool[p1] & pool[p2])==0)
        {
        //byte at p1 works with byte at p2.
        }
    }//for p2
}//for p1

Так, каковы мои варианты? Словарь не поможет мне (я думаю), потому что, если у меня есть свой байт поиска 0001 0001 Я не хочу найти такой байт: XXX0 XXX0

Есть идеи? Большое спасибо за вашу помощь;

Я приветствую C #, C ++ или любой псевдокод. Я ищу алгоритм; не так уж много кода

Mike

mcdowella · Answer 1 · 19 сентября 2011

Одним из довольно общих решений является «транспонирование битов» ваших данных таким образом, чтобы у вас был, например, кусок слов, содержащий все старшие биты ваших данных, кусок слов, содержащий все биты на одну позицию оттуда,и так далее.Затем для вашего двухбитного запроса вы или вместе два таких куска слов и ищите 0 битов - так что если слово результата равно -1, вы можете полностью пропустить его.Чтобы узнать, где все 0 битов находятся в слове x, посмотрите на popcnt (x ^ (x + 1)): если x = ... 10111, то x + 1 = ... 11000, поэтому x ^ (x + 1)= 000..01111 - и popcnt сообщит вам, где находится самый низкий порядок 0.На практике большой выигрыш может быть, когда большая часть ваших данных не удовлетворяет запросу, и вы можете пропустить целые слова: когда у вас много совпадений, стоимость запроса по любой схеме может быть небольшой по сравнению со стоимостью чего бы то ни былопланирую делать со спичками.В базе данных это http://en.wikipedia.org/wiki/Bitmap_index - там много информации и указателей на исходный код.

Существует множество идей для запроса данных 0/1 в разделе 6.5 Кнута 2 - «Двоичные данные».атрибуты».Большинство из них требуют от вас некоторого представления о распределении ваших данных, чтобы понять, где они применимы.Одна идея оттуда обычно применима - если у вас есть какая-либо древовидная структура или структура индекса, вы можете хранить в узлах древовидной информации информацию о / или обо всем, что находится под ней.Затем вы можете сравнить свой запрос с этой информацией, и иногда вы можете обнаружить, что ничто под этим узлом не может соответствовать вашему запросу, и в этом случае вы можете пропустить все это.Это, вероятно, наиболее полезно, если между битами есть связи, например, если вы разделяете пул, просто сортируя его и разрезая его на куски, даже биты, которые не влияют на деление на куски, всегда устанавливаются в некоторых кусках и никогдаустановить в других кусках.

harold · Answer 2 · 19 сентября 2011

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

Поместите весь пул в диаграмму двоичных решений с нулевым подавлением.Элементы из pool должны быть наборами, где индексы, для которых бит равен 1, являются элементами этого набора.ZDD - это семейство всех этих наборов.
Чтобы выполнить запрос, сформируйте другой ZDD - семейство всех наборов, которые не включают биты, равные 1 в seek (которые будут маленьким ZDD втерминами узлов), затем перечислите все множества в пересечении этих ZDD.

Перечисление всех этих множеств из пересечения является алгоритмом, чувствительным к выходу, но вычисление пересечения требует времени в зависимости от того, насколько велики ZDD, поэтомухорошо ли это работает, зависит от того, является ли pool хорошим ZDD (запрос zdd определенно хорош).И, конечно, вы должны подготовить этот ZDD, так что в любом случае это поможет, только если вы планируете часто запрашивать один и тот же пул.

Louis Ricci · Answer 3 · 19 сентября 2011

Самое замечательное в байтах - это всего 256 возможностей.

Вы могли бы изначально создать 2d массив 256x256, а затем просто просмотреть массив с двумя значениями.

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

static bool[256,256] LookUp = {
 {true, true, true ... },
 ...
 {false, false, false ...}
};

static bool IsUsefule(byte a, byte b) {
 return LookUp[a][b];
}

изменить * Или используйте Массивы ответа Массивы

Внутренний массив будет содержать ТОЛЬКО байты, которые являются «полезными».

static List<<byte[]> LookUp = new List<byte[]>(256);

static byte[] IsUseful(byte a) {
 return LookUp[a];
}

Если 'a' = 0, то IsUseful вернет 255 байтов с установленным битом. Это позволит избежать вашего внутреннего цикла из вашего примера.

saxi · Answer 4 · 24 сентября 2011

Прежде всего, мой английский плохой, но я надеюсь, что вы понимаете.Кроме того, я знаю, что мой ответ немного запоздал, но я думаю, что все еще полезен.Как кто-то указал, лучшее решение - создать справочную таблицу.Для этого вам необходимо жестко закодировать каждый случай итерации цикла в массиве.К счастью, мы работаем с байтами, поэтому возможно только 256 случаев.Например, если мы возьмем ваш список шаблонов {3, 6, 12, 48}, мы получим эту таблицу:

0: { 3, 6, 12, 48 }
1: { 6, 12, 48 }
2: { 12, 48 }
3: { 12, 48 }
3: { 12, 48 }

    ...

252: { 3 }
253:   -
254:   -
255:   -

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

Реализация:

Я использовал Python для генерации двух файлов заголовков.Один с определением таблицы поиска, другой с желаемыми значениями списка шаблонов.Затем я включаю этот файл в новый проект C и все!

Python Code

#! /usr/bin/env python

from copy import copy
from time import *
import getopt
import sys


class LUPattern:
    __LU_SZ = 256

    BASIC_TYPE_CODE = "const uint8_t"
    BASIC_ID_CODE = "p"
    LU_ID_CODE = "lu"
    LU_HEADER_CODE = "__LUPATTERN_H__"
    LU_SZ_PATTLIST_ID_CODE = "SZ" 
    PAT_HEADER_CODE = "__PATTERNLIST_H__"
    PAT_ID_CODE = "patList"


    def __init__(self, patList):
        self.patList = copy(patList)


    def genLU(self):
        lu = []

        pl = list( set(self.patList) )
        pl.sort()

        for i in xrange(LUPattern.__LU_SZ):
            e = []
            for p in pl:
                if (i & p) == 0:
                    e.append(p)
            lu.append(e)

        return lu


    def begCode(self):
        code = "// " + asctime() + "\n\n" \
            + "#ifndef " + LUPattern.LU_HEADER_CODE + "\n" \
            + "#define " + LUPattern.LU_HEADER_CODE + "\n" \
            + "\n#include <stdint.h>\n\n" \

        return code


    def luCode(self):
        lu = self.genLU()
        pDict = {}

        luSrc = LUPattern.BASIC_TYPE_CODE \
            + " * const " \
            + LUPattern.LU_ID_CODE \
            + "[%i] = { \n\t" % LUPattern.__LU_SZ

        for i in xrange(LUPattern.__LU_SZ):
            if lu[i]:
                pId = "_%i" * len(lu[i])
                pId = pId % tuple(lu[i]) 
                pId = LUPattern.BASIC_ID_CODE + pId

                pBody = "{" + "%3i, " * len(lu[i]) + " 0 }"
                pBody = pBody % tuple(lu[i])

                pDict[pId] = pBody
                luSrc += pId
            else:
                luSrc += "0"

            luSrc += (i & 3) == 3 and (",\n\t") or ", "

        luSrc += "\n};"

        pCode = ""
        for pId in pDict.keys():
            pCode +=  "static " + \
                LUPattern.BASIC_TYPE_CODE + \
                " " + pId + "[] = " + \
                pDict[pId] + ";\n"

        return (pCode, luSrc)        


    def genCode(self):
        (pCode, luSrc) = self.luCode()
        code = self.begCode() \
            + pCode + "\n\n" \
            + luSrc + "\n\n#endif\n\n"

        return code    


    def patCode(self):
        code = "// " + asctime() + "\n\n" \
            + "#ifndef " + LUPattern.PAT_HEADER_CODE + "\n" \
            + "#define " + LUPattern.PAT_HEADER_CODE + "\n" \
            + "\n#include <stdint.h>\n\n"
        code += "enum { " \
            + LUPattern.LU_SZ_PATTLIST_ID_CODE \
            + " = %i, " % len(self.patList) \
            + "};\n\n"
        code += "%s %s[] = { " % ( LUPattern.BASIC_TYPE_CODE, 
                                   LUPattern.PAT_ID_CODE )
        for p in self.patList:
            code += "%i, " % p
        code += "};\n\n#endif\n\n"


        return code



#########################################################


def msg():
    hmsg = "Usage: "
    hmsg += "%s %s %s"  % (
        sys.argv[0], 
        "-p", 
        "\"{pattern0, pattern1, ... , patternN}\"\n\n")
    hmsg += "Options:"

    fmt = "\n%5s, %" + "%is" % ( len("input pattern list") + 3 )
    hmsg += fmt % ("-p", "input pattern list")

    fmt = "\n%5s, %" + "%is" % ( len("output look up header file") + 3 )
    hmsg += fmt % ("-l", "output look up header file")

    fmt = "\n%5s, %" + "%is" % ( len("output pattern list header file") + 3 )
    hmsg += fmt % ("-f", "output pattern list header file")

    fmt = "\n%5s, %" + "%is" % ( len("print this message") + 3 )
    hmsg += fmt % ("-h", "print this message")

    print hmsg

    exit(0)


def getPatternList(patStr):
    pl = (patStr.strip("{}")).split(',')
    return [ int(i) & 255  for i in pl ]


def parseOpt():
    patList = [ 255 ] # Default pattern
    luFile = sys.stdout
    patFile = sys.stdout

    try:
        opts, args = getopt.getopt(sys.argv[1:], "hp:l:f:", ["help", "patterns="])
    except getopt.GetoptError:
        msg()

    for op in opts:
        if op[0] == '-p':
            patList = getPatternList(op[1])
        elif op[0] == '-l':
            luFile = open(op[1], 'w')
        elif op[0] == '-f':
            patFile = open(op[1], 'w')
        elif op[0] == '-h':
            msg()

    return (patList, luFile, patFile)    


def main():
    (patList, luFile, patFile)  = parseOpt()
    lug = LUPattern(patList)
    print >> luFile , lug.genCode()
    print >> patFile, lug.patCode()

    patFile.close()
    luFile.close()


if __name__ == "__main__":
    main()

C Code

Теперь, после выполнения скрипта выше, он сгенерирует два файла: lu.h и pl.h.Мы должны включить эти файлы в наш новый C-проект.Вот простой пример кода C:

#include "pl.h"
#include "lu.h"
#include <stdio.h>


int main(void)
{
  uint32_t stats[SZ + 1] = { 0 };
  uint8_t b;

  while( fscanf(stdin, "%c", &b) != EOF )
  {
    (void)lu[b];
    // lu[b] has bytes that don't match with b
  }

  return 0;
}

Тест и тест:

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

Я делаю две одинаковые версии одной и той же утилиты.Один использует таблицу поиска (версия noloop), другой использует типичный цикл (версия цикла).код цикла немного отличается от кода noloop, но я стараюсь минимизировать эти различия.

версия noloop :

#include "pl.h"
#include "lu.h"
#include <stdio.h>


void doStats(const uint8_t * const, uint32_t * const);
void printStats(const uint32_t * const);


int main(void)
{
  uint32_t stats[SZ + 1] = { 0 };
  uint8_t b;

  while( fscanf(stdin, "%c", &b) != EOF )
  {
    /* lu[b] has pattern values that not match with input b */
    doStats(lu[b], stats);
  }
  printStats(stats);

  return 0;
}


void doStats(const uint8_t * const noBitMatch, uint32_t * const stats)
{
  uint8_t i, j = 0;

  if(noBitMatch)
  {
    for(i = 0; noBitMatch[i] != 0; i++)
      for(; j < SZ; j++)
        if( noBitMatch[i] == patList[j] )
        {
          stats[j]++;
          break;
        }
  }
  else
    stats[SZ]++;

}


void printStats(const uint32_t * const stats)
{
  const uint8_t * const patList = lu[0];
  uint8_t i;

  printf("Stats: \n");
  for(i = 0; i < SZ; i++)
    printf("  %3i%-3c%9i\n", patList[i], ':', stats[i]);
  printf("  ---%-3c%9i\n", ':', stats[SZ]);
}

версия цикла:

#include "pl.h"
#include <stdio.h>
#include <stdint.h>
#include <string.h>


void getNoBitMatch(const uint8_t, uint8_t * const);
void doStats(const uint8_t * const, uint32_t * const);
void printStats(const uint32_t * const);


int main(void)
{
  uint8_t b;
  uint8_t noBitMatch[SZ];
  uint32_t stats[SZ + 1] = { 0 };

  while( fscanf(stdin, "%c", &b ) != EOF )
  {     
    getNoBitMatch(b, noBitMatch);
    doStats(noBitMatch, stats); 
  }
  printStats(stats);

  return 0;
}


void doStats(const uint8_t * const noBitMatch, uint32_t * const stats)
{
  uint32_t i;
  uint8_t f;

  for(i = 0, f = 0; i < SZ; i++)
  {
    f = ( (noBitMatch[i]) ? 1 : f );    
    stats[i] += noBitMatch[i];
  }

  stats[SZ] += (f) ? 0 : 1;
}


void getNoBitMatch(const uint8_t b, uint8_t * const noBitMatch)
{
  uint8_t i;

  for(i = 0; i < SZ; i++)
    noBitMatch[i] = ( (b & patList[i]) == 0 ) ? 1 : 0;
}


void printStats(const uint32_t * const stats)
{
  uint8_t i;

  printf("Stats: \n");
  for(i = 0; i < SZ; i++)
    printf("  %3i%-3c%9i\n", patList[i], ':', stats[i]);
  printf("  ---%-3c%9i\n", ':', stats[SZ]);
}

Оба кода выполняют одно и то же действие: подсчитывают байты, которые не совпадают с конкретным байтом списка шаблонов (pl.h).

Makefile для их компиляции:

###

CC = gcc
CFLAGS = -c -Wall
SPDUP = -O3
DEBUG = -ggdb3 -O0
EXECUTABLE = noloop
AUXEXEC = loop

LU_SCRIPT = ./lup.py
LU_HEADER = lu.h
LU_PATLIST_HEADER = pl.h

#LU_PATLIST = -p "{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }"
#LU_PATLIST = -p "{ 3, 6, 12, 15, 32, 48, 69, 254 }"
LU_PATLIST = -p "{ 3, 6, 12, 48 }"
#LU_PATLIST = -p "{ 1, 2 }"
#LU_PATLIST = -p "{ 1 }"
LU_FILE = -l $(LU_HEADER)
LU_PAT_FILE = -f $(LU_PATLIST_HEADER)


SRC= noloop.c loop.c

SOURCE = $(EXECUTABLE).c
OBJECTS = $(SOURCE:.c=.o)

AUXSRC = $(AUXEXEC).c
AUXOBJ = $(AUXSRC:.c=.o)


all: $(EXECUTABLE) $(AUXEXEC)

lookup:
    $(LU_SCRIPT) $(LU_PATLIST) $(LU_FILE) $(LU_PAT_FILE)
    touch $(SRC)

$(EXECUTABLE): lookup $(OBJECTS)
    $(CC) $(OBJECTS) -o $@

$(AUXEXEC): $(AUXOBJ)
    $(CC) $(AUXOBJ) -o $@

.c.o:
    $(CC) $(CFLAGS) $(SPDUP) -c $<

debug: lookup dbg
    $(CC) $(OBJECTS) -o $(EXECUTABLE)
    $(CC) $(AUXOBJ) -o $(AUXEXEC)

dbg: *.c
    $(CC) $(CFLAGS) $(DEBUG) -c $<

clean:
    rm -f $(EXECUTABLE) $(AUXEXEC) *.o &> /dev/null

.PHONY: clean

В качестве входного потока я использовал три простых текста: простой текст gpl v3, простой текст Святой Библии и исходные коды ядра Linux, используя рекурсивный инструмент cat.Выполнение этого кода с другим списком шаблонов даст мне следующие результаты:

Sat Sep 24 15:03:18 CEST 2011


 Test1:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:      18917
    2:      22014
    3:      12423
    4:      19015
    5:      11111
    6:      12647
    7:       7791
    8:      23498
    9:      13637
   10:      16032
   11:       9997
   12:      14059
   13:       9225
   14:       8609
   15:       6629
   16:      25610
  ---:          0

real    0m0.016s
user    0m0.008s
sys     0m0.016s

 Loop version:
------------------------
Stats: 
    1:      18917
    2:      22014
    3:      12423
    4:      19015
    5:      11111
    6:      12647
    7:       7791
    8:      23498
    9:      13637
   10:      16032
   11:       9997
   12:      14059
   13:       9225
   14:       8609
   15:       6629
   16:      25610
  ---:          0

real    0m0.020s
user    0m0.020s
sys     0m0.008s


 Test2:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:    3392095
    2:    3970343
    3:    2325421
    4:    3102869
    5:    1973137
    6:    2177366
    7:    1434363
    8:    3749010
    9:    2179167
   10:    2751134
   11:    1709076
   12:    2137823
   13:    1386038
   14:    1466132
   15:    1072405
   16:    4445367
  ---:       3310

real    0m1.048s
user    0m1.044s
sys     0m0.012s

 Loop version:
------------------------
Stats: 
    1:    3392095
    2:    3970343
    3:    2325421
    4:    3102869
    5:    1973137
    6:    2177366
    7:    1434363
    8:    3749010
    9:    2179167
   10:    2751134
   11:    1709076
   12:    2137823
   13:    1386038
   14:    1466132
   15:    1072405
   16:    4445367
  ---:       3310

real    0m0.926s
user    0m0.924s
sys     0m0.016s


 Test3:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:  222678565
    2:  254789058
    3:  137364784
    4:  239010012
    5:  133131414
    6:  146334792
    7:   83232971
    8:  246531446
    9:  145867949
   10:  161728907
   11:  103142808
   12:  147836792
   13:   93927370
   14:   87122985
   15:   66624721
   16:  275921653
  ---:   16845505

real    2m22.900s
user    3m43.686s
sys     1m14.613s

 Loop version:
------------------------
Stats: 
    1:  222678565
    2:  254789058
    3:  137364784
    4:  239010012
    5:  133131414
    6:  146334792
    7:   83232971
    8:  246531446
    9:  145867949
   10:  161728907
   11:  103142808
   12:  147836792
   13:   93927370
   14:   87122985
   15:   66624721
   16:  275921653
  ---:   16845505

real    2m42.560s
user    3m56.011s
sys     1m26.037s


 Test4:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:      12423
    6:      12647
   12:      14059
   15:       6629
   32:       2338
   48:       1730
   69:       6676
  254:          0
  ---:      11170

real    0m0.011s
user    0m0.004s
sys     0m0.016s

 Loop version:
------------------------
Stats: 
    3:      12423
    6:      12647
   12:      14059
   15:       6629
   32:       2338
   48:       1730
   69:       6676
  254:          0
  ---:      11170

real    0m0.021s
user    0m0.020s
sys     0m0.008s


 Test5:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:    2325421
    6:    2177366
   12:    2137823
   15:    1072405
   32:     425404
   48:     397564
   69:    1251668
  254:          0
  ---:    1781959

real    0m0.969s
user    0m0.936s
sys     0m0.048s

 Loop version:
------------------------
Stats: 
    3:    2325421
    6:    2177366
   12:    2137823
   15:    1072405
   32:     425404
   48:     397564
   69:    1251668
  254:          0
  ---:    1781959

real    0m1.447s
user    0m1.424s
sys     0m0.032s


 Test6:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:  137364784
    6:  146334792
   12:  147836792
   15:   66624721
   32:   99994388
   48:   64451562
   69:   89249942
  254:       5712
  ---:  105210728

real    2m38.851s
user    3m37.510s
sys     1m26.653s

 Loop version:
------------------------
Stats: 
    3:  137364784
    6:  146334792
   12:  147836792
   15:   66624721
   32:   99994388
   48:   64451562
   69:   89249942
  254:       5712
  ---:  105210728

real    2m32.041s
user    3m36.022s
sys     1m27.393s


 Test7:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:      12423
    6:      12647
   12:      14059
   48:       1730
  ---:      11277

real    0m0.013s
user    0m0.016s
sys     0m0.004s

 Loop version:
------------------------
Stats: 
    3:      12423
    6:      12647
   12:      14059
   48:       1730
  ---:      11277

real    0m0.014s
user    0m0.020s
sys     0m0.000s


 Test8:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:    2325421
    6:    2177366
   12:    2137823
   48:     397564
  ---:    1850018

real    0m0.933s
user    0m0.916s
sys     0m0.036s

 Loop version:
------------------------
Stats: 
    3:    2325421
    6:    2177366
   12:    2137823
   48:     397564
  ---:    1850018

real    0m0.892s
user    0m0.860s
sys     0m0.052s


 Test9:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    3:  137364784
    6:  146334792
   12:  147836792
   48:   64451562
  ---:  132949214

real    2m31.187s
user    3m31.289s
sys     1m25.909s

 Loop version:
------------------------
Stats: 
    3:  137364784
    6:  146334792
   12:  147836792
   48:   64451562
  ---:  132949214

real    2m34.942s
user    3m33.081s
sys     1m24.381s


 Test10:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:      18917
    2:      22014
  ---:       6639

real    0m0.014s
user    0m0.016s
sys     0m0.008s

 Loop version:
------------------------
Stats: 
    1:      18917
    2:      22014
  ---:       6639

real    0m0.017s
user    0m0.016s
sys     0m0.008s


 Test11:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:    3392095
    2:    3970343
  ---:     881222

real    0m0.861s
user    0m0.848s
sys     0m0.032s

 Loop version:
------------------------
Stats: 
    1:    3392095
    2:    3970343
  ---:     881222

real    0m0.781s
user    0m0.760s
sys     0m0.044s


 Test12:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:  222678565
    2:  254789058
  ---:   84476465

real    2m29.894s
user    3m30.449s
sys     1m23.177s

 Loop version:
------------------------
Stats: 
    1:  222678565
    2:  254789058
  ---:   84476465

real    2m21.103s
user    3m22.321s
sys     1m24.001s


 Test13:  test/gpl.txt (size: 35147)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:      18917
  ---:      16230

real    0m0.015s
user    0m0.020s
sys     0m0.008s

 Loop version:
------------------------
Stats: 
    1:      18917
  ---:      16230

real    0m0.016s
user    0m0.016s
sys     0m0.008s


 Test14:  test/HolyBible.txt (size: 5918239)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:    3392095
  ---:    2526144

real    0m0.811s
user    0m0.808s
sys     0m0.024s

 Loop version:
------------------------
Stats: 
    1:    3392095
  ---:    2526144

real    0m0.709s
user    0m0.688s
sys     0m0.040s


 Test15:  test/linux-kernel-3.0.4 (size: 434042620)
---------------------------------------------------

 Look up table version:
------------------------
Stats: 
    1:  222678565
  ---:  201900739

real    2m21.510s
user    3m23.009s
sys     1m23.861s

 Loop version:
------------------------
Stats: 
    1:  222678565
  ---:  201900739

real    2m22.677s
user    3m26.477s
sys     1m23.385s


Sat Sep 24 15:28:28 CEST 2011

Выводы:

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

Skizz · Answer 5 · 19 сентября 2011

Единственное, о чем я могу подумать, это сократить количество тестов:

for(int p1=1; p1<pool.Length; p1++)
{
  for(int p2=0; p2<p1; p1++)
  {
    if((pool[p1] & pool[p2])==0)
    {
      //byte at p1 works with byte at p2.
      //byte at p2 works with byte at p1.
    }
  }
}

поразрядно не в байтовом сравнении

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 5 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Реализация:

Python Code

C Code

Тест и тест:

Выводы:

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

поразрядно не в байтовом сравнении

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 5 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Реализация:

Python Code

C Code

Тест и тест:

Выводы:

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы