WordCount в Sublime

Sub­lime чудесен. Можно сказать, что проблема отсутствия под lin­ux-ом Notepad++ успешно решена.

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

Соответствующий плагин нашёлся сразу, но он не умел посчитывать количество символов. Решил допилить, а заодно разобраться, что у этих плагинчиков внутри.

В результате – целый вечер открытий и удивительных экспериментов. Удивился встроенной консоли, попутно оптимизировал код и исправил баг с полем read_time в настройках.

Обновлённый код успешно merged и залит в основную ветку.

А удивил меня сам алгоритм подсчёта. Их там целых два, причём первый закомментирован:

#=====1
# wrdRx = Pref.wrdRx
# """counts by counting all the start-of-word characters"""
# # regex to find word characters
# matchingWrd = False
# words = 0
# for ch in content:
# # # test if this char is a word char
# isWrd = wrdRx(ch)
# if isWrd and not matchingWrd:
# words = words + 1
# matchingWrd = True
# if not isWrd:
# matchingWrd = False
#=====2
wrdRx = Pref.wrdRx
words = len([x for x in content.replace('n', ' ').split(' ') if False == x.isdigit() and wrdRx(x)])

На первый вгляд, алгоритм 1 должен работать лучше и экономней. Фактически, перед нами нечто наподобие state machine, и его сложность не больше o(n). В то время как второй алгоритм создаёт кучу новых элементов только для того, чтобы их пересчитать.

На самом деле алгоритм 2 отрабатывает намного быстрее, чем 1. Например, чтобы подсчитать количество слов в “Петербургских трущобах” Крестовского, 2-ому нужно порядка 1 сек., а первому – 2.

Вот вам и оптимизация.

C++: Счастливый билет с длинной арифметикой

Счастливый трамвайный билет — это такой, у которого сумма первых трёх цифр номера равна сумме трёх последних. При встрече его полагается съесть.

Сколько таких билетов всего? Какова вероятность встретить счастливый?

Алгоритм для этих вычислений в Википедии настолько ужасен, что народ с Хабра довольно быстро породил в комментариях огромное количество вариантов на C++, Perl и… SQL.

Я тоже не смог пройти мимо и написал считалку на C++ с арифметикой указателей и поддержкой длинной арифметики. При желании она может считать хоть 12-значные числа.

Оптимизировал всем, о чём пишут в пособиях для начинающих. Получилась миниатюрная машина Тьюринга, которая бегает указателем по числам и считает разряды:

void inline count_lucky(unsigned int num_length_val)
{
  bool is_odd = (num_length_val % 2) > 0;
  unsigned int num_length = (is_odd) ? num_length_val - 1 : num_length_val;
  register unsigned int lucky=1, total=pow(10.0,(int)num_length), i;
  char *num = new char[num_length], *end=num+(num_length-1);
  register char *pos=end;
  for(i=0; i < num_length; i++)
    num[i]=0;
  while(pos>=num)
  {
     if((*pos)<9)
     {
        (*pos)++;
        if(pos==end)
        {
           if(is_lucky((unsigned char*)num, num_length))
             lucky++;
        }
        else
          pos++;
     }
     else
     {
       *pos=-1;
       pos--;
     }
  }
  printf("Lucky are %d of %d (%.3f%%)n",(is_odd) ? lucky * 10 : lucky, (is_odd) ? total * 10 : total,((float)lucky/total*100));
  delete[] num;
}
bool inline is_lucky(unsigned char* items, unsigned int items_count)
{
  unsigned char val1=0, val2=0;
  unsigned int half = items_count >> 1;
  for(unsigned int i=0; i < half; i++)
  {
    val1 += items[i];
    val2 += items[items_count-1-i];
  }
  return (val1==val2);
}

Увы! Как показывает практика, уже на 7-значном билете тупой перебор, развёрнутый и оптимизированный компилятором, оказывается эффективней. Похоже, компилятор попросту выполняет сам большую часть явно заданных вычислений.
В этом легко убедиться, запустив тест хотя бы для 7 разрядов:

void inline count_lucky(unsigned int num_length);
bool inline is_lucky(unsigned char* items, unsigned int items_count);
int _tmain(int argc, _TCHAR* argv[])
{
  clock_t start = clock(), mine;
  count_lucky(7);
  mine=clock();
  printf("Mine time was: %dn", (mine - start));
  count_lucky_fromwiki();
  printf("His time was: %dn", (clock() - mine));
  return 0;
}

void count_lucky_fromwiki()
{
  int total=0,lucky=0;
  for(int i1=0; i1<10; i1++)
    for(int i2=0; i2<10; i2++)
      for(int i3=0; i3<10; i3++)
        for(int i4=0; i4<10; i4++)
          for(int i5=0; i5<10; i5++)
            for(int i6=0; i6<10; i6++)
              for(int i7=0; i7<10; i7++, total++)
                if(i1+i2+i3 == i5+i6+i7)
                  lucky++;
   printf("Lucky are %d of %d (%.3f%%)n",lucky,total,((float)lucky/total*100));
}

Человек уже не может обогнать машину :(. Слава роботам!

В качестве утешения — на 8 вложенный циклах валился компилятор из Bor­land C++ Builder 6.

JavaScript: Случайные элементы массива

Родилось из C#-овой, но на JavaScript наглядней.

Нужно выбрать из массива N случайных элементов. Как это сделать быстро?

Если длина массива <= N — это очевидно. А если нет? Сначала склонируем массив:

Object.prototype.clone = function() {
var newObj = (this instanceof Array) ? [] : {};
for (i in this) {
  if (i == 'clone') continue;
  newObj[i] = (this[i] && typeof this[i] == "object") ? this[i].clone() : this[i];
  return newObj;
};

Потом создадим новый массив и скопируем в него нужное число элементов, а из оригинала удалим:

function selectRemoveAdd(arr, max)
{
 var arrLength = arr.length;
 if(max >= arrLength)
  return arr.clone();
 var newArray = [];
 var cloneArray = arr.clone();
 var i = 0, newPos = 0;
 while(i++ < max)
 {
  newPos = getRandom(arrLength);
  newArray.push(cloneArray[newPos]);
  cloneArray.splice(newPos, 1);
  arrLength--;
 }
 return newArray;
}

Такой вариант обычно предлагают на форумах. Но зачем создавать ещё одни массив? Можно взять исходный и удалить всё лишнее:

var arrLength = arr.length;
 if(max >= arrLength)
  return arr.clone();
 var newArray = arr.clone();
 while(arrLength-- > max)
  newArray.splice(getRandom(arrLength), 1);
 return newArray;

Какой вариант быстрее? Правильный ответ, что быстрее оба, но по-разному. Если N меньше arr.length / 2, то первый, если больше — то второй. Поэтому самый красивый и правильный способ — это:

function selectRemoveOnly(arr, max)
{
 var arrLength = arr.length;
 var newArray = arr.clone();
 while(arrLength-- > max)
   newArray.splice(getRandom(arrLength), 1);
 return newArray;
}
function selectRemoveAdd(arr, max)
{
 var arrLength = arr.length;
 var newArray = [];
 var cloneArray = arr.clone();
 var i = 0, newPos = 0;
 while(i++ < max)
 {
  newPos = getRandom(arrLength);
  newArray.push(cloneArray[newPos]);
  cloneArray.splice(newPos, 1);
  arrLength--;
 }
 return newArray;
}
function selectOptimised(arr, max)
{
 if(max >= arr.Length)
  return arr.clone();
 if(max <= arr.length / 2)
  return selectRemoveAdd(arr, max);
 else
  return selectRemoveOnly(arr, max);
}

И работать будет просто замечательно:

JavaScript: быстрые циклы

length в JavaScript — штука медленная. Это очень хорошо видно по скорости выполнения циклов. Вовремя заменив for на while, можно получить выигрыш в производительности в 7 раз.

В умелых руках циклы JavaScript прекрасно заменяют друг друга. А значит, есть повод дополнить старый постинг о среднем арифметическом.

var digitRegEx=/^-?d+([,.]d+)?$/g;
function arithmeticMean() {
  var len = arguments.length, i = len, finalSum = 0;
  (!i) && return 0;
  while (i--)
    if (digitRegEx.test(arguments[i]))
      finalSum += parseFloat(arguments[i]);
  return (len) ? finalSum / len : 0;
}

Кстати, как народная, так и более-менее проектная реализация всяких дополнительных функций для IE грешат for по lenght и ужасающе медленным trim(). Если руки дойдут — надо бу исправить.

JavaScript: быстрый парсинг числа

Как вы думаете, как быстрее парсить число с плавающей точкой — вот так:

function isNumber(n) {
    if (n == null) return null;
    var num_parsed = parseFloat(n);
    return (!isNaN(num_parsed) && isFinite(n)) ?  true : false;
}

Или так (reg­Exp немного исправлен по сравнению с примером с суммой, чтобы уважить сербов):

var digitRegEx=/^-?d+([,.](d+)?)?$/g;
function isNumberRegExp(n) {
    return digitRegEx.test(n);
}

По идее, reg­Exp должен работать медленней. А на самом деле скорость почти одинакова. Такие дела.