• Какой поисковый алгоритм используют поисковые системы?

    Viverov
    @Viverov
    Как то сел формализировать свои знания и на пол пути забил, дико неинтересное и муторное занятие. Для тех кто в начале пути, пригодиться для систематизации знаний о информационном поиске, можете продолжить начатую работу.
    https://yadi.sk/i/OqHvc21HngMRb

    Начинать лучше с детализации индексов, их штук 9 с детальным описанием. Ну и если циклично пойти раз в 6-7 разрастется схемка.
    Ответ написан
    4 комментария
  • План подготовки для поступления в Яндекс ШАД?

    @Mercury13
    Программист на «си с крестами» и не только
    Алгоритмы. Немного олимпиадного программирования ОЧЕНЬ не помешает. Алгоритмы там предлагают несложные, но очень нетривиальные, надо чувствовать, как решить задачу. Элементы сложности алгоритмов. Две задачи из восьми гарантированно будут.

    Алгебра и дискретная математика. Первый курс, всё скопом, без доказательств. Линейные уравнения, квадратичные формы, матрицы, собственные векторы, жорданова форма, перестановки, графы, теория множеств, комбинаторика, алгебра логики…

    Интегралы (не слишком «злые», но приёмы «подстановка», «по частям» и «тригонометрический интеграл» всё же освоить стоит). Интеграл средней сложности — постоянный гость в ШАДý. Может быть и ещё одна задача из мутьанализа — но это как повезёт и задача будет гарантированно нетривиальная, но решающаяся на «том, что помнишь с института» — дифференцирование, ряды Тейлора, основы топологии, простейшие пределы, правило Лопиталя. Вспомни, как берутся простейшие двойные интегралы, может попасться, например, на теории вероятностей.

    ФКП. Самое начало. Аналитических функций и рядов Лорана точно не будет. А вот то, что в комплексном поле многочлен n-й степени имеет n корней, знать надо.

    Теория вероятностей. Непрерывные и дискретные вероятности. Нечто несложное, почти что на уровне кубиков и карт, но одна-две из восьми будет. Хотя статистика — важная часть ШАДа, на экзамене не требуют. И пекла типа белых шумов и интегралов Ито не будет. Хотя что-то типа дискретной марковской цепи — а вдруг, хотя знакомые мне три экзамена не было.

    Школьные олимпиадные задачи. Возможна одна.

    Итого.
    Две — алгоритмы.
    Одна-две — вероятность.
    Одна — интеграл.
    Две-три — что угодно из школьной математики, дискретной математики, матанализа, алгебры, ФКП…

    P.S. Очень хороший приём, который мне помог. Конечно, вам придётся держать скан какого-нибудь справочника или распечатку Википедии (это не возбраняется, но электроника запрещена — впрочем, калькулятора задачи не требуют). Печатайте на одной стороне, вторую — на черновик!
    Ответ написан
    4 комментария
  • Python многопоточность Requests, что блокирует обработку?

    bzzzzzz
    @bzzzzzz
    Блокирует обработку в вашем случае не GIL, а то, как вы распределяете задачи между потоками: вы перед началом работы распределяете все урлы поровну между потоками и, поэтому, складывается такая ситуация, когда часть потоков простаивает и ждет когда один из них проверит все оставшиеся ему сайты. В своей программе вы должны использовать очереди для распределения задач и, конечно же, сократить количество I/O операций.

    Код будет приблизительно таким (смотрите мои комментарии для того, чтобы понять что и почему):

    # coding=utf-8
    import requests
    import time
    import os
    from threading import Thread, current_thread
    from Queue import Queue
    
    
    theard_count = 25
    
    
    domain_file = "domains.txt"
    domain_temp = "temp"
    
    
    def check_url(host):
        url = 'http://' + host
    
        try:
            requests.get(url, timeout=5)
        except Exception:
            return False
        else:
            return True
    
    
    def run(queue, result_queue):
        # Цикл продолжается пока очередь задач не станет пустой
        while not queue.empty():
            # получаем первую задачу из очереди
            host = queue.get_nowait()
            print '{} checking in thread {}'.format(host, current_thread())
            # проверяем URL
            status = check_url(host)
            # сохраняем результат для дальнейшей обработки
            result_queue.put_nowait((status, host))
            # сообщаем о выполнении полученной задачи
            queue.task_done()
            print '{} finished in thread {}. Result={}'.format(host, current_thread(), status)
    
        print '{} closing'.format(current_thread())
    
    
    # MAIN
    def main():
        start_time = time.time()
    
        # Для получения задач и выдачи результата используем очереди
        queue = Queue()
        result_queue = Queue()
    
        fr_success = os.path.join(domain_temp, "req-good.txt")
        fr_errors  = os.path.join(domain_temp, "req-error.txt")
    
        # Сначала загружаем все URL из файла в очередь задач
        with open(domain_file) as f:
            for line in f:
                queue.put(line.strip())
    
        # Затем запускаем необходимое количество потоков
        for i in range(theard_count):
            thread = Thread(target=run, args=(queue, result_queue))
            thread.daemon = True
            thread.start()
    
        # И ждем, когда задачи будут выполнены    
        queue.join()
    
        # После чего пишем результаты в файлы
        with open(fr_success, 'w') as fs, open(fr_errors, 'w') as fe:
            while not result_queue.empty():
                status, host = result_queue.get_nowait()
    
                if status:
                    f = fs
                else:
                    f = fe
    
                f.write(host)
                f.write('\n')
    
        print time.time() - start_time
    
    if __name__ == '__main__':
        main()


    500 сайтов, из которых 150 не работают, он парсит за 35 секунд.
    Ответ написан
    3 комментария