Jon Bentley в Столбце 1 его книги, программируя жемчуг представляет технику для сортировки последовательности ненулевых положительных целых чисел с помощью битовый векторов.
Я взял программу bitsort.c отсюда и вставил ее ниже:
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* bitsort.c -- bitmap sort from Column 1
* Sort distinct integers in the range [0..N-1]
*/
#include
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i)
{
int sh = i>>SHIFT;
a[i>>SHIFT] |= (1<<(i & MASK));
}
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }
int main()
{ int i;
for (i = 0; i < N; i++)
clr(i);
/*Replace above 2 lines with below 3 for word-parallel init
int top = 1 + N/BITSPERWORD;
for (i = 0; i < top; i++)
a[i] = 0;
*/
while (scanf("%d", &i) != EOF)
set(i);
for (i = 0; i < N; i++)
if (test(i))
printf("%d\n", i);
return 0;
}
Я понимаю то, что функции сбрасывают, устанавливают и тестируют, делают и объясняют их ниже: (исправьте меня, если я неправ здесь).
Теперь, я не понимаю, как функции делают то, что они делают. Я не могу выяснить всю побитовую обработку, происходящую в тех трех функциях.
Первые 3 константы взаимосвязаны. BITSPERWORD - 32. Это нужно установить в зависимости от вашего компилятора и архитектуры. SHIFT равен 5, потому что 2 ^ 5 = 32. Наконец, MASK - это 0x1F, что равно 11111 в двоичном формате (то есть: все нижние 5 бит установлены). Эквивалентно MASK = BITSPERWORD - 1.
Битовый набор концептуально представляет собой просто массив бит. Эта реализация фактически использует массив int и предполагает 32 бита на int. Поэтому всякий раз, когда мы хотим установить, очистить или протестировать (прочитать) бит, нам нужно выяснить две вещи:
Поскольку мы предполагаем, что на int 32 бита, мы можем просто разделить на 32 (и усечь), чтобы получить нужный нам индекс массива. Деление на 32 (BITSPERWORD) аналогично сдвигу вправо на 5 (SHIFT). Вот что такое бит a [i >> SHIFT]. Вы также можете записать это как [i / BITSPERWORD] (и на самом деле вы, вероятно, получите такой же или очень похожий код, если у вашего компилятора есть разумный оптимизатор).
Теперь, когда мы знаем, какой элемент мы хотим , нам нужно выяснить, какой бит. На самом деле мы хотим остаток. Мы могли бы сделать это с помощью i% BITSPERWORD, но оказывается, что i & MASK эквивалентны. Это потому, что BITSPERWORD - это степень 2 (в данном случае 2 ^ 5), а MASK - это все 5 нижних битов.
The bit magic is used as a special addressing scheme that works well with row sizes that are powers of two.
If you try understand this (note: I rather use bits-per-row than bits-per-word, since we're talking about a bit-matrix here):
// supposing an int of 1 bit would exist...
int1 bits[BITSPERROW * N]; // an array of N x BITSPERROW elements
// set bit at x,y:
int linear_address = y*BITSPERWORD + x;
bits + linear_address = 1; // or 0
// 0 1 2 3 4 5 6 7 8 9 10 11 ... 31
// . . . . . . . . . . . . .
// . . . . X . . . . . . . . -> x = 4, y = 1 => i = (1*32 + 4)
The statement linear_address = y*BITSPERWORD + x
also means that x = linear_address % BITSPERWORD
and y = linear_address / BITSPERWORD
.
When you optimize this in memory by using 1 word of 32 bits per row, you get the fact that a bit at column x can be set using
int bitrow = 0;
bitrow |= 1 << (x);
Now when we iterate over the bits, we have the linear address, but need to find the corresponding word.
int column = linear_address % BITSPERROW;
int bit_mask = 1 << column; // meaning for the xth column,
// you take 1 and shift that bit x times
int row = linear_address / BITSPERROW;
So to set the i'th bit, you can do this:
bits[ i%BITSPERROW ] |= 1 << (linear_address / BITSPERROW );
An extra gotcha is, that the modulo operator can be replaced by a logical AND, and the / operator can be replaced by a shift, too, if the second operand is a power of two.
a % BITSPERROW == a & ( BITSPERROW - 1 ) == a & MASK
a / BITSPERROW == a >> ( log2(BITSPERROW) ) == a & SHIFT
This ultimately boils down to the very dense, yet hard-to-understand-for-the-bitfucker-agnostic notation
a[ i >> SHIFT ] |= ( 1 << (i&MASK) );
But I don't see the algorithm working for e.g. 40 bits per word.
Я решил использовать Csv Reader Себастьяна Лориона.
Предложение Джея Риггса также является отличным решением, но мне просто не нужны были все функции, которые предоставляет Общий синтаксический анализатор Эндрю Риссинга .
После использования Csv Reader Себастьяна Лориона в мой проект в течение почти полутора лет, я обнаружил, что он вызывает исключения при синтаксическом анализе некоторых файлов CSV, которые я считаю правильно сформированными.
Начиная с set ():
Сдвиг вправо на 5 аналогичен делению на 32. Он позволяет определить, в каком int находится бит.
МАСКА равна 0x1f или 31. Операция И с адресом дает битовый индекс в int. Это то же самое, что и остаток от деления адреса на 32.
Сдвиг 1 влево на битовый индекс ("1 << (i & MASK)") приводит к целому числу, которое имеет только 1 бит в заданном наборе позиции.
Операция ИЛИ устанавливает бит.
Строка «int sh = i >> SHIFT;» является потраченной впустую строкой, потому что они не использовали sh снова под ней, а вместо этого просто повторяли «i >> SHIFT»
clr () в основном то же самое, что и set, за исключением того, что вместо OR с 1 << (i & MASK), чтобы установить бит, он выполняет операцию И с инверсией, чтобы очистить бит. test () И с 1 << (i & MASK) для проверки бита.
Битовая сортировка также удалит дубликаты из списка, потому что она будет считать до 1 на целое число. Сортировка, которая использует целые числа вместо битов для подсчета более одного каждого из них, называется поразрядной сортировкой.
Несколько сомнений: 1. Зачем нужна 32 бита? 2. Можем ли мы сделать это на Java, создав HashMap с ключами от 0000000 до 9999999 и значения 0 или 1 в зависимости от наличия / отсутствия бита? Каковы последствия для такой программы?