Skip to content

Instantly share code, notes, and snippets.

@dobrokot
dobrokot / fast_grep_patch2.diff
Created August 25, 2013 00:56
faster state sets merge in grep utility, dfa.c (avoid O(N^2) algorithms)
--- dfa.c.back 2013-08-05 16:53:47.824514544 +0400
+++ dfa.c 2013-08-25 04:23:18.783885918 +0400
@@ -1992,6 +1992,115 @@
s->elems[i] = s->elems[i + 1];
}
+/* merge implementation of sorted sets, then number of sets smore than 2
+ priority queue aka 'heap' data structure used to select maximum of
+ many elements */
+
@dobrokot
dobrokot / cpp_iostream_fail_open_file.cpp
Created August 17, 2013 20:01
How to handle non-existing opened file with ifstream ?
#include <iostream>
#include <fstream>
int main() {
std::ifstream empty("empty.txt");
std::ifstream no_file("no_file.txt");
std::cout << "bool: " << (empty?"e 1":"e 0") << ' ' << (no_file?"n 1":"n 0") << '\n';
std::cout << "rdstate:" << (empty.rdstate()?"e 1":"e 0") << ' ' << (no_file.rdstate()?"n 1":"n 0") << '\n';
@dobrokot
dobrokot / fast-python-utf8.cpp
Created August 6, 2013 19:07
faster conversion to unicode from UTF-8 for python 2.*
#include <Python.h>
#include <stdlib.h>
#include <stdio.h>
#define UTF8_ACCEPT 0
#define UTF8_REJECT 1
#include <stdint.h>
$diff -u ~/tmp/grep-2.14/src/dfa.c.prev ~/tmp/grep-2.14/src/dfa.c
--- /home/dobrokot/tmp/grep-2.14/src/dfa.c.prev 2013-08-05 16:53:47.824514544 +0400
+++ /home/dobrokot/tmp/grep-2.14/src/dfa.c 2013-08-05 16:50:41.435058597 +0400
@@ -1978,6 +1978,52 @@
m->elems[m->nelem++] = s2->elems[j++];
}
+static void
+merge_inplace (position_set const *src, position_set *dst)
+{
@dobrokot
dobrokot / fuzzy_search.py
Last active December 20, 2015 14:59
fuzzy search regexp generator
# usage:
# LC_ALL=C grep "$(python fuzzy_search.py "HELLO")" input.file.utf8.txt
import sys
s = sys.argv[1]
su = s.decode('utf-8')
utf8_any = '[^\x80-\xbf][\x80-\xbf]*'
@dobrokot
dobrokot / exceptions.cpp
Created July 9, 2013 10:45
exceptions.cpp
#include <iostream>
#include <string>
#include <stdexcept>
#include <stdlib.h>
void g(int i) {
if (i % 4 == 0 && i % 6 == 0)
throw std::logic_error("FATALITY");
if (i % 3 == 0)
print "hello, world"
@dobrokot
dobrokot / primes_ulam_spiral_rotated45.py
Created June 21, 2013 11:06
# ulam spiral, rotate 45 degree
# ulam spiral, rotate 45 degree
# http://users.livejournal.com/_winnie/392996.html
import Image
def is_prime(n):
if n <= 2:
return 1
k = 2
@dobrokot
dobrokot / iospeed.cpp
Created March 13, 2013 11:35
Testing speed of ofstream and FILE*
#include <iostream>
#include <fstream>
#include <stdio.h>
const int N = 1000*1000*10;
void f1() {
std::ofstream out("out.txt", std::ios::binary);
for (int i = 0; i < N; ++i) {
#!/usr/bin/env python
import pylab as pl
import numpy as np
import random
import sys
stat = {}