About Blog |

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

Теорема:


Любой детерминированный алгоритм поиска в отсортированном массиве основанный на операции сравнения в худшем случае работает как минимум время log[2]n

Определение:

Алгоритм поиска основанный на операции сравнения получает на вход массив размера N и искомый элемент X. Алгоритм может получать информацию о конфигурации массива производя только сравнения искомого элемента с элементами массива, результатом операции сравнения могут быть только два исхода (больше, меньше).


Для принятия дальнейших решений алгоритм использует собранную информацию о сравнениях.

На выходе алгоритм выдаст номер индекса от 1 до N в случае если он нашел элемент, или 0 если не нашел. Таким образом алгоритм выдает N+1 возможное значение.

Доказательство:

Обозначим через K максимальное количество сравнений, выполнив которые алгоритм завершит работу.

Под сравнениями понимаются сравнения элемента X с какими либо элементами массива или элементов массива друг с другом.
Всего возможно 2^K различных исходов ответов при K сравнениях.
Выход алгоритма определяется последовательностью ответов на K сравнений к моменту его завершения.
Т.е выполняясь по шагам от 1 до К алгоритм оставляет за собой "шлейф" из ответов на сравнения.
Каждая комбинация исходов ответов приводит к конкретному результату (завершению алгоритма) который выдает одно из возможных N+1 выходных значений (фиксированный выход детерминирован фиксированными ответами).

Одна и та же комбинация ответов не может привести к разным исходам, по причине детерминированности алгоритма. Каждому возможному N+1 выходу должна соответствовать как минимум одна уникальная комбинация ответов.

Таким образом количество комбинаций последовательных исходов ответов на вопросы должно быть 2^K>=N+1 . Если бы это неравенство не выполнялось то существовал бы хотя бы один возможный вариант выхода (из N+1 возможных) такой что для него не нашлось бы комбинации ответов. Это бы означало, что в массиве существовал бы элемент, который алгоритм бы не смог найти, а это противоречит тому что мы рассматриваем алгоритм, который находит любой элемент присутствующий в массиве.

Логарифмируя неравенство получаем K>log[2]N

Таким образом мы нашли нижнюю границу алгоритма для худшего случая

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


Примечание:

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

Автор статьи: Евгений Малов

отдаем статику django сервером

if settings.DEBUG:
    from django.conf.urls.static import static
    from django.contrib.staticfiles.urls import staticfiles_urlpatterns
    urlpatterns += static(settings.MEDIA_URL, document_root=settings.MEDIA_ROOT)
    urlpatterns += staticfiles_urlpatterns()

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

отдельно: /home/ /var/ogs /var/ /tmp еще можно отельно винт под Mysql файлы и т.д For multi-user systems or systems with lots of disk space, it's best to put /usr, /var, /tmp, and /home each on their own partitions separate from the / partition.

MySQL: SELECTFOR UPDATE

Бывают случаи, когда приходится обновлять данные в MySQL, сделав предварительно выборку из неё, чтобы получить актуальные значения полей. Однако, в "боевых" условиях, когда идет обработка сразу нескольких конкурирующих запросов, следует учитывать возможность "вклинивания" запроса с паралельной транзакции, между запросами SELECT и UPDATE. В условиях полной синхронизации обновление могло-бы выглядеть примерно так: SELECT ammount FROM products WHERE product_id=1; ... UPDATE products SET ammount=<новое значение> WHERE product_id=1; Но как уже было сказано, в реальных условиях между данными запросами запросто может вклиниться запрос из паралельного потока, работающего с теми-же данными. Если между запросами SELECT и UPDATE произойдет обновление данных, о котором вы не знаете, то значения полей, которые вы получили из запроса SELECT потеряют свою актуальность, а значит их дальнейшее обновление может привести к потере данных. Обволакивание запросов в транзакцию может не помочь, поскольку по-умолчанию в MySQL, транзакции работают используя уровень изоляции REPEATABLE READ, который допускает делать обычные SELECT одновременно. Есть конечно вариант, перевести уровень в SERIALIZABLE, но в нем нет особого смысла, если вам нужно заблокировать только один SELECT. Для этого будет лучше использовать запрос SELECT ... FOR UPDATE: SELECT ammount FROM products WHERE product_id=1 FOR UPDATE; ... UPDATE products SET ammount=<новое значение> WHERE product_id=1; Однако нужно учитывать, что для того, чтобы получить синхронизацию, другие транзакции также должны делать SELECT .. FOR UPDATE, иначе синхронизация не будет гарантирована.

MySQL: READ COMMITTED vs SERIALIZABLE

Как известно в MySQL (InnoDB) по умолчанию используется уровень изоляции транзакций REPEATABLE READ. Как он работает мы рассмотрели в прошлой статье. Однако кроме REPEATABLE READ в MySQL есть еще и другие уровни, такие как READ COMMITTED и SERIALIZABLE. Уровень READ COMMITTED отличается от REPEATABLE READ тем, что текущая транзакция получает доступ к изменениям, внесенным другой транзакцией, сразу-же, как только будет сделан их COMMIT. Как вы помните, в REPEATABLE READ вы будете видеть только тот снимок (snapshot) базы, который существовал в момент начала транзакции. В остальном READ COMMITTED работает точно также, как и REPEATABLE READ, т.е паралельные транзакции могут одновременно делать неблокирующие SELECT, не мешая друг другу. Конечно, это может иногда, привести к неожиданым результатам, что и было показано в прошлой статье. Блокирующие запросы (UPDATE, DELETE) работают синхронно (т.е ожидают освобождения блокировки). Уровень SERIALIZABLE отличается от READ COMMITTED и REPEATABLE READ тем, что когда он включен, ко всем запросам SELECT добавляется LOCK IN SHARE MODE. Это означает, что запросы SELECT ставят блокировку и если другая транзакция попытается сделать тоже самое, работая в таком же уровне изоляции (либо в другом уровне изоляции, но используя блокирующий запрос), то ей придется подождать окончания первой транзакции, если строка была модифицирована. Однако, следует избегать использования длинных транзакций, чтобы уменьшить вероятность истечения таймаута ожидания освобождения блокировки (последнее, кстати, касается всех уровней изоляции). Помимо REPEATABLE READ, READ COMMITTED и SERIALIZABLE в MySQL есть еще один уровень изоляции - READ UNCOMMITTED. Из самого его названия ясно, что он отличается от READ COMMITTED тем, что позволяет видеть изменения внесенные конкурирующей транзакцией не дожидаясь когда будет сделан COMMIT. Этот уровень изоляции еще называют "dirty read", т.е грязное чтение. Думаю, что и так понятно, что работать в этом режиме можно, только если целостность данных для вас не так уж и важна. В большинстве случаев, уровень изоляции установленный в MySQL по-умолчанию, справляется со своей задачей вполне приемлемо и менять его следует только, в крайнем случае и только, если вы точно знаете, что хотите получить и чем готовы пожертвовать (это может быть как и производительность, так и сами данные).

SQL: транзакции увеличивают скорость выполнения множественных запросов

SQL: транзакции увеличивают скорость выполнения множественных запросов Как показывают бенчмарки, транзакции в большинстве случаев увеличивают скорость выполнения множественных запросов, которые идут один за другим. Причем прирост в скорости может быть десятикратным. В основном это касается запросов на вставку новых строк и обновления старых. Запросы на выборку данных такого прироста не дают. Объясняется этот феномен очень просто. Дело в том, что программисты для того чтобы увеличить скорость выборки данных, добавляют в таблицу индексы, которые помогают осуществлять поиск данных значительно быстрее. Но за это, конечно-же приходится платить свою цену. Чем больше индексов содержит таблица, тем медленнее будет происходить обновление данных, т.е запросы INSERT и UPDATE будут работать медленнее за счет того, что при обновлении таблицы будет происходить и обновление индексов. Соответственно, при множественных запросах, идущих один за другим, большое количество времени расходуется на обновление индексов. Если-же запросы однотипные, то нет никакого смысла после каждого запроса обновлять индексы, это можно сделать после того, как все запросы будут выполнены. Достичь этого можно, как раз если перед началом серии запросов открыть транзакцию. Таким образом, индексы обновляться не будут, пока все запросы транзакции не будут завершены. В результате, общее время на выполнение серии запросов значительно снижается (до 10 раз). Конечно-же, проделать такое с таблицами MyISAM не получится, поскольку они не поддерживают транзакции, но вот с таблицами InnoDB - вполне реально.

подсчет числа файлов в каталоге

ls | tee /dev/stderr | wc -l
find -type f|cat -n

Блокировка записей в реляционных БД

Блокировка при использовании реляционных БД.
Если вы используете реляционные базы данных, можно использовать "LOCK" механизм для блокировки доступа к критичным секциям.
В то время когда одна "SELECT FOR UPDATE" транзакция лочит строку, другая "SELECT FOR UPDATE" с этой строкой будет ждать конца 1 транзакции.
# You can use any Python DB API.
[SQL] BEGIN;
[SQL] SELECT col_name FROM table_name where id = 1 FOR UPDATE;

[Process some python code]

[SQL] COMMIT;

блокировка критичных секций в python

  1 import os
  2
  3 class SingleRun():
  4     class InstanceRunningException(Exception):
  5         pass
  6     def __init__(self, lock_file):
  7         #define the lock file name
  8         self.lock_file =  "/tmp/%s.pid" % lock_file
  9     def __call__(self, func):
 10         def f(*args, **kwargs):
 11             if os.path.exists(self.lock_file):
 12                 #get process id, if lock file exists
 13                 pid = open(self.lock_file, "rt").read()
 14                 if not os.path.exists("/proc/%s" % pid):
 15                     #if process is not alive remove the lock file
 16                     os.unlink(self.lock_file)
 17                 else:
 18                     #process is running
 19                     raise self.InstanceRunningException(pid)
 20             try:
 21                 #store process id
 22                 open(self.lock_file, "wt").write(str(os.getpid()))
 23                 #execute wrapped function
 24                 func(*args,**kwargs)
 25             finally:
 26                 if os.path.exists(self.lock_file):
 27                     os.unlink(self.lock_file)
 28         return f


Пример

  1 @SingleRun(lock_file="x")
  2 def a():
  3     pass
  4
  5 @SingleRun(lock_file="x")
  6 def b():
  7     pass
  8
  9 @SingleRun(lock_file="y")
 10 def c():
 11     pass
http://krosinski.blogspot.com/2012/04/preventing-python-script-from-running.html
http://stackoverflow.com/questions/1123200/how-to-lock-a-critical-section-in-django
http://code.activestate.com/recipes/519626/
import os
import fcntl

class DjangoLock:

    def __init__(self, filename):
        self.filename = filename
        # This will create it if it does not exist already
        self.handle = open(filename, 'w')

    # flock() is a blocking call unless it is bitwise ORed with LOCK_NB to avoid blocking 
    # on lock acquisition.  This blocking is what I use to provide atomicity across forked
    # Django processes since native python locks and semaphores only work at the thread level
    def acquire(self):
        fcntl.flock(self.handle, fcntl.LOCK_EX)

    def release(self):
        fcntl.flock(self.handle, fcntl.LOCK_UN)

    def __del__(self):
        self.handle.close()

Usage:

lock = DJangoLock('/tmp/djangolock.tmp')
lock.acquire()
try:
    pass
finally:
    lock.release()

python else

В питоне else применим не только для if, но также и для for и try.
for i in foo:
    if i == 0:
        break
else:
    print("i was never 0. Вызов будет если break не был вызван")

same as:

found = False
for i in foo:
    if i == 0:
        found = True
        break
if not found: 
    print("i was never 0")
try:
  do()
except Exception:
  print "Catch!"
else:
  print "Если не был пойман эксепшен - выполнится этот код внутри else!"
finally:
  end()