Сортировку подсчётом решил сделать и на Python и на OCaml. Просто было интересно, записать процесс работы и посмотреть потом со стороны.

#!/usr/bin/env python
# -*- coding: utf-8 -*-


import random


def counting_sort(data, min_number, max_number):
    n = max_number - min_number + 1  # [0, n]
    counters = [0] * n

    for v in data:
        counters[v - min_number] += 1

    result = []
    for v, count in enumerate(counters):
        result.extend([v + min_number] * count)

    return result


def create_test_data(size):
    min_number = random.randint(-10, 10)
    max_number = random.randint(min_number + 1, 15)
    data = [random.randint(min_number, max_number) for _ in range(size)]
    return data, min_number, max_number


def main():
    for size in range(10):
        data, min_number, max_number = create_test_data(size)
        sorted_by_counting_sort = counting_sort(data, min_number, max_number)
        sorted_by_sorted = sorted(data)
        if sorted_by_counting_sort != sorted_by_sorted:
            print('Error!')
            print('Test data:     {}'.format(data))
            print('Counting sort: {}'.format(sorted_by_counting_sort))
            print('Sorted:        {}'.format(sorted_by_sorted))
            break
        elif size < 15:
            print('Ok for size {}'.format(size))
            print('Test data:     {}'.format(data))
            print('Counting sort: {}'.format(sorted_by_counting_sort))
            print()
    else:
        print('Ok!')


if __name__ == '__main__':
    main()

~ Upload failed: Sorry, your asciicast is too big.
~ Retry later by running: asciinema upload ./tmp9e2k0bwd-asciinema.json

open Core.Std


let counting_sort = function
    | [] -> []
    | data -> (
        let min_elt = match List.min_elt data compare with
        | Some i -> i
        | None -> assert false
        in
        let max_elt = match List.max_elt data compare with
        | Some i -> i
        | None -> assert false
        in
        let n = max_elt - min_elt + 1 in
        let counters = Array.create n 0 in

        let rec count = function
        | [] -> ()
        | h :: tl -> (
            counters.(h - min_elt) <- (counters.(h - min_elt) + 1);
            count tl;
        )
        in

        count data;

        Array.foldi counters ~init:[] ~f:(fun i accum v -> accum @ Array.to_list (Array.create v (i + min_elt)))
    )


let rec create_test_data = function
    | 0 -> []
    | size -> (Random.int 10) - 5 :: create_test_data (size - 1)


let () =
    for i = 0 to 10 do
        let data = create_test_data i in
        let sorted_by_count = counting_sort data in
        let sorted_by_std = List.sort data ~cmp:compare in
        if sorted_by_count <> sorted_by_std then
            (
                printf "Error\n";
                data |> List.to_string ~f:string_of_int |> printf "Data: %s\n";
                sorted_by_count |> List.to_string ~f:string_of_int |> printf "Count: %s\n";
                sorted_by_std |> List.to_string ~f:string_of_int |> printf "Std: %s\n\n";
            )
        else
            (
                printf "Ok\n";
                data |> List.to_string ~f:string_of_int |> printf "Data:  %s\n";
                sorted_by_count |> List.to_string ~f:string_of_int |> printf "Count: %s\n";
                sorted_by_std |> List.to_string ~f:string_of_int |> printf "Std:   %s\n\n";
            )
    done

Обычно при запуске веб-проектов на python асинхронные задачи в фоне выполняются при помощи Celery. Но в этот раз у меня на сервере был uwsgi, а разворачивать celery для одной-двух задач мне не хотелось. Поэтому решил посмотреть на uwsgidecorators и его spool.

Проект на сервере разработан на django, но запускать такую большую штуку только для тестирования spool было перебором, а тут рядом была открыта страница с документацией по Falcon. Вот так у меня появился подопытный фреймворк.

Быстро написал скрипт для запуска задачи в фоне. Задача запускалась, в терминал через каждую секунду асинхронно сыпались print('hi'). После этого стал налаживать обмен данными между обработчиком запроса и задачей. Придумал "задачу", в которой обработчик запроса должен создавать в словаре хеш от даты, а потом асинхронно считать сумму кодов символов в этом хеше.

Первый пример, который должен был работать

import hashlib
import json

from datetime import datetime

import falcon

from uwsgidecorators import spool


storage = {}


@spool
def _task(arguments):
    key = arguments['key']
    storage[key] = sum(ord(ch) for ch in key)


class Handler(object):
    def on_get(self, req, resp):
        key = hashlib.md5(str(datetime.now()).encode('utf-8')).hexdigest()
        storage[key] = None

        _task.spool(key=key)

        resp.body = json.dumps({'storage': storage})


serv = falcon.API()
serv.add_route('/', Handler())

Запуск сервера из командной строки

uwsgi --http :9111 --wsgi-file sample.py --callable serv --master --spooler ./spool

Но пример не работал, а выдавал в браузер:

{

    "storage": {
        "77e609faa5ca12e6fc37273bf07f9308": null,
        "0cfc5e83db37eb0eedf989aa0e894f63": null,
    }

}

Закралось подозрение, что uwsgi создаёт разные объекты для _storage. Проверил id:

@spool
def _task(arguments):
    key = arguments['key']
    _storage[key] = sum(ord(ch) for ch in key)

    print('=' * 80)
    print(id(_storage))
    print(_storage)
    print('=' * 80)


class Handler(object):
    def on_get(self, req, resp):
        key = hashlib.md5(str(datetime.now()).encode('utf-8')).hexdigest()
        _storage[key] = None

        _task.spool(key=key)

        resp.body = json.dumps({'storage': _storage})
        print('-' * 80)
        print(id(_storage))
        print(_storage)
        print('-' * 80)

ID объектов были одинаковые.

--------------------------------------------------------------------------------
140613325993160
{'7ca17ee5c8cd055f8cebd19c0e44a393': None, '8c7e86712679f74574396e02c6af5e4e': None}
--------------------------------------------------------------------------------
================================================================================
140613325993160
{'7ca17ee5c8cd055f8cebd19c0e44a393': 2388, '8c7e86712679f74574396e02c6af5e4e': 2130}
================================================================================

Но где-то же была ошибка. Проверил номер процесса:

@spool
def _task(arguments):
    key = arguments['key']

    print('=' * 80)
    print(os.getpid())
    print('=' * 80)

    _storage[key] = sum(ord(ch) for ch in key)


class Handler(object):
    def on_get(self, req, resp):
        key = hashlib.md5(str(datetime.now()).encode('utf-8')).hexdigest()
        _storage[key] = None

        _task.spool(key=key)

        resp.body = json.dumps({'storage': _storage})
        print('-' * 80)
        print(os.getpid())
        print('-' * 80)

А вот номера процессов отличались. Как так получилось, что совпали айдишники объектов - не знаю. Нужно посмотреть, как конкретно запускается spooler в uwsgi.

Вот так не получилось по-быстрому сделать пример обмена данными между задачей и обработчиком запроса. Тут стоит сказать, что пересылать между ними обычные объекты не получится. Но азарт заставил задуматься над способом обмена данными.

В живом проекте для этих целей, вероятнее всего, использовалась бы база данных. Здесь выдумывать что-то другое не стал, взял sqlite, к которой с давних пор отношусь с теплотой.

Для начала разделил задачи и приложение на два отдельных файла, раз уж под них идут разные процессы.

# -*- coding: utf-8 -*-

import falcon
import hashlib
import json
import sqlite3

from datetime import datetime

from tasks import hashsum


class Handler(object):
    def __init__(self):
        self.db = sqlite3.connect('storage.sqlite3')

        cur = self.db.cursor()
        cur.execute('CREATE TABLE IF NOT EXISTS keys (key TEXT, val INTEGER)')
        self.db.commit()

    def add_key(self, key):
        cur = self.db.cursor()
        cur.execute('INSERT INTO keys (key) values(?)', (key, ))
        self.db.commit()

    def get_data(self):
        data = {}
        cur = self.db.cursor()
        for key, val in cur.execute('SELECT key, val FROM keys'):
            data[key] = val
        self.db.commit()
        return data

    def on_get(self, req, resp):
        key = hashlib.md5(str(datetime.now()).encode('utf-8')).hexdigest()
        self.add_key(key)

        resp.body = json.dumps({'db': self.get_data()})

        hashsum.spool(key=key)


serv = falcon.API()
serv.add_route('/', Handler())

# -*- coding: utf-8 -*-

import sqlite3

from uwsgidecorators import spool


@spool
def hashsum(arguments):
    key = arguments['key']
    val = sum(ord(ch) for ch in key)

    db = sqlite3.connect('storage.sqlite3')
    cur = db.cursor()
    cur.execute('UPDATE keys SET val=? WHERE key=?', (val, key))
    db.commit()
    db.close()

Тут я увидел, что текущая директория для процессов разная, как результат два разных файла базы данных. Нужно было выносить настройки в отдельный файл. Так появился settings.py

import os

DB_NAME = os.path.join(
    os.path.dirname(os.path.abspath(__file__)),
    'storage.sqlite3')

# -*- coding: utf-8 -*-

import sqlite3

from uwsgidecorators import spool

from settings import DB_NAME


@spool
def hashsum(arguments):
    key = arguments['key']
    val = sum(ord(ch) for ch in key)

    db = sqlite3.connect(DB_NAME)
    cur = db.cursor()
    cur.execute('UPDATE keys SET val=? WHERE key=?', (val, key))
    db.commit()
    db.close()

# -*- coding: utf-8 -*-

import falcon
import hashlib
import json
import sqlite3

from datetime import datetime

from settings import DB_NAME
from tasks import hashsum


class Handler(object):
    def __init__(self):
        self.db = sqlite3.connect(DB_NAME)

        cur = self.db.cursor()
        cur.execute('CREATE TABLE IF NOT EXISTS keys (key TEXT, val INTEGER)')
        self.db.commit()

    def add_key(self, key):
        cur = self.db.cursor()
        cur.execute('INSERT INTO keys (key) values(?)', (key, ))
        self.db.commit()

    def get_data(self):
        data = {}
        cur = self.db.cursor()
        for key, val in cur.execute('SELECT key, val FROM keys'):
            data[key] = val
        self.db.commit()
        return data

    def on_get(self, req, resp):
        key = hashlib.md5(str(datetime.now()).encode('utf-8')).hexdigest()
        self.add_key(key)

        resp.body = json.dumps({'db': self.get_data()})

        hashsum.spool(key=key)


serv = falcon.API()
serv.add_route('/', Handler())

Всё заработало как надо. Результат работы в браузере:

{

    "db": {
        "35f3fd25fc8abea97908b13854cfc813": 2300,
        "da90ec1480702833e9f16d6ea3d59a7a": 2243,
        "d70719f8adb446aa04accf8f12cd8984": null,
        "23a06eda818e0abae56c58498e4bb4c1": 2330
    }

}

Вот так получилось, что к приложению на мини-фреймворке пришлось прикручивать файл настроек, чтобы запустить задачу в фоне.

На самом деле, нужно посмотреть, как похожие задачи решают сами разработчики Falcon, потому что я пошёл по явно "джанговскому" пути. Просто очень много работаю с Django, вот и привык к таким его частям, как файл настроек.

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

Так вот, на checkio.org в блоге написали и про моё решение к задаче The best number ever. Я там под ником @grigoriytretyakov. Ну и раз уж решение попало в общий доступ, то продублирую его и здесь.

def checkio():
    i = 16

    in_hex_has_only_1_and_0 = not bool(set(hex(i)[2:]) - set('01'))

    oct_twice_bigger_than_hex_in_10_radix = int(oct(i)[2:]) / int(hex(i)[2:]) == 2.0

    convert_to_hex_to_str_give_two_in_bin = int(hex(i)[2:], 2)

    count_of_0_in_4_times = bin(i)[2:].count('0') / hex(i)[2:].count('0')

    and_2_in_power_4_give_stil_16 = 2 ** count_of_0_in_4_times

    best_number = (
        in_hex_has_only_1_and_0 and
        oct_twice_bigger_than_hex_in_10_radix and
        convert_to_hex_to_str_give_two_in_bin and
        count_of_0_in_4_times == 4 and
        and_2_in_power_4_give_stil_16 == 16
    )

    if best_number:
        return i

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

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

>>> dir
<built-in function dir>
>>> ^[[A
  File "<stdin>", line 1
    ^
SyntaxError: invalid syntax
>>>

Нужно установить readline для сборки

sudo apt-get install libreadline-dev

А потом обычный набор

wget https://www.python.org/ftp/python/3.4.3/Python-3.4.3.tar.xz

tar xf Python-3.4.3.tar.xz
cd Python-3.4.3/

./configure --prefix=/opt/python3.4.3 --with-ensurepip=install
make && sudo make install

После этого предыдущая команда начнёт работать

>>> dir
<built-in function dir>
>>> dir
<built-in function dir>
>>>