LINUX.ORG.RU

7
Всего сообщений: 21

Насколько часто используются segment(interval) trees в программировании

Насколько часто segment trees/interval trees и запросы по ним используются в коммерческом программировании, в open source проектах и на каких языках программирования чаще всего?

На англоязычных форумах пишут, что segment trees/interval trees (рекурсивный или нерекурсивный подход) достаточно популярны в соревнованиях по программированию.

А как обстоят дела на практике, которая, возможно, имеет мало общего со спортивным программированием?

Перемещено maxcom из general

 ,

hibiscusM ()

Является ли такая реализация правильной?

Задача.

Имеются запросы в форме tuple of ints например

 
q=(1,5)  No1 query
q=(2,3)  No2 query
q=(3,1)  No3 query

q[0] может быть 1 или 2 или 3
q[1] - любое положительное число

Условия (по-англ. короче)
array=[ ]
if q[0]==1, insert q[1] to array
if q[0]==2, remove q[1] from array
if q[0]==3, check if there is integer whose frequency is q[1] in array

Количество запросов: 1<= queries <= 10**9

Является ли это правильным решением, если удалять запрошенные числа не по мере поступления запроса с q[0]=2, а сформировать сначала два независимых списка (один с числами для добавления, а другой с числами ждя удаления) и удалять, когда придет запрос с q[0]=3? И является ли решение с генераторами приемлемым или это странное решение?

def freqQuery(queries):
    from collections import Counter

    output=[]
    ad = Counter()
    de = Counter()
    for k,v in queries:
        if k==3:
            ad=ad-de
            if v in ad.values():
                output+=[1]
            else:
                output+=[0]
        elif k==2:
             de.update([v])
        else:
             ad.update([v])

    return output

def freqQuery(queries):
    from collections import Counter

    def helper(k, v, ad, de):

        if k==1:
            ad.update([v])   # add value as key & count its frequency only for No 1 queries
        elif k==2:
            de.update([v])   # add value as key & count its frequency only for No2 queries
        return ad-de         # remove all integers of No2 quaries from Counter related to No 1 queries


    a = Counter()
    d = Counter()

    #list of final arrays in the form of generator to analyze No 3 queries
    # such list includes Counters , tuples of Counter and int related to No 3 query
    gen=(helper(key, value, a, d) if key !=3 else (a, value) for key,value in queries)

    # list of tuples in the form of generator
    gen2=(item for item in gen if type(item) == tuple)

    #form final output
    gen3=(1 if item[1] in item[0].values() else 0 for item in gen2)

    return list(gen3)


 , , ,

hibiscusM ()

понятно ли написана функция(и)?

Эта функция принимает список и корневой узел и формирует binary search tree, каждый раз - разное.


def create_lists(dic, ls, node):   #creates left and right lists for a node & updates a dict
    ind=ls.index(node.data)
    ls1=(ls[:ind]) # can be empty, no index error
    ls2=ls[ind+1:]  # can be empty, no index error

    dic[node]=(ls1, ls2)
    return dic


def create_childs (dic, node):   #creates left and right childs for a parent & updates a dict
    import random

    if dic[node][0]:
        intL=random.choice(dic[node][0])
        node.left=Node(intL)
        dic=create_lists(dic, dic[node][0], node.left)



    if dic[node][1]:
        intR=random.choice(dic[node][1])
        node.right=Node(intR)
        dic=create_lists(dic, dic[node][1], node.right)


    del dic[node]

    return dic


def bin_srch_tr(ls, root):
    # ls must be sorted in increased order!
    print(root)

    import random

    dic=dict()
    dic=create_lists(dic, ls, root)
    dic = create_childs(dic, root)

    while dic:
        dic2=dic.copy()
        for node in dic:
            print('node' , node.data, dic) # current node & all node objects with left & right lists per node in a dic
            dic2 = create_childs(dic2, node)
        dic=dic2

    return root


ls=[1,2,3,4,5,6,7]
root=Node(4)  # root where data is int, left & right are None  

print(bin_srch_tr(ls, root))

 , , ,

hibiscusM ()

тесты с сайта hackerrank и собственный тест показывают разные результаты

Может ли быть, что отдельные тесты на сайте hackerrank составлены некорректно?

Задача с сайта. Проверить является ли дерево binary search tree. Если не является, то ответ False.

Все тесты с сайта, которые проверяют ответ False показывают, что у моя ф. дает ответ True.

Спецально была написана фнукция, которая формирует дерево в проивольном порядке, т.е. оно не binary search tree. После этого ф. которая проверяет такое дерево, проверялась моим собственым тестом и ответ постоянно False, т.е. такой какой и требуется.

Мне на первый взгляд непонятно, что у меня не так написано. Может, кто подскажет?

    def __comp__(self):
        l = self.left
        r = self.right
        if l and r:
            if l.right:
                extra = l.right
                if extra and not extra.data.__lt__(self.data) and not extra.data.__lt__(r.data):
                    return False, 'NO'
            return l.data.__lt__(self.data) and r.data.__gt__(self.data), 'LR'
        elif l:
            return l.data.__lt__(self.data), 'L'
        elif r:
            return r.data.__gt__(self.data), 'R'
        elif not r and not l:
            return True, 'END'

 def check_binary_search_tree_(root):
    nodes = root.__comp__()
    if not nodes[0]: return False
    dic = dict()
    if 'L' in nodes[1]: dic[root.left] = 'lwing'
    if 'R' in nodes[1]: dic[root.right] = 'rwing'

    while dic:
        new_dic = dict()
        for node in dic:
            nodes = node.__comp__()
            if not nodes[0]: return False
            if 'R' in nodes[1]:
                new_dic[node.right] = dic[node]
                if new_dic[node.right] == 'lwing' and not node.right.__lt__(root):
                    return False
            if 'L' in nodes[1]:
                new_dic[node.left] = dic[node]
                if new_dic[node.left] == 'rwing' and not node.left.__gt__(root):
                    return False
        dic = new_dic
    return True


def Checker(tree, func):
    assert func(tree)==False
    return 'OK'


print(Checker(form_tree(ls),check_binary_search_tree_))

 

 , ,

hibiscusM ()

Странное поведение функции, которая формирует дерево

Пишу ф. form_tree, которая принимает параметр - список и формирует на его основе дерево в произвольной форме.

Пока функция в стадии доработки и отладки.
Это черновой вариант. Ф. linker - «helper function», тоже в стадии доработки.

class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


    def insertL(self, data):
        self.left = node(data)
        return self.left

    def insertR(self, data):
        self.right = node(data)
        return self.right

linker

def linker(root, lst):
    import random


    seq = ['left', 'right', 'nither', 'either']
    res = random.choices(seq,(0.2, 0.2, 0.1, 0.5), k=1)
    if lst:
        l=random.choice(lst)

        if res == ['left']:
            root=root.insertL(l)
            lst.remove(l)
            return root, lst
        elif res == ['right']:
            root=root.insertR(l)
            lst.remove(l)
            return root,lst
        elif res == ['nither']:
            return root,lst
        elif res == ['either']:
            print('res', res)
            nodes = [root.insertL(l)]
            lst.remove(l)
            if lst:
                l2=random.choice(lst)
                nodes+=[root.insertR(l2)]
                lst.remove(l2)
                return nodes, lst
            else:
                return nodes[0],lst
    else:
        return root, lst

основная

def form_tree(ls):
    import random

    data = random.choice(ls)
    root=Root=node(data)
    ls.remove(data)
    nodes = None

    while ls:
        if type(nodes)!= list:
            result=linker(root, ls)
            if not result[1]:
                return Root
            else:
                ls=result[1]
            if type(result[0])!= list:
                root=result[0]
            else:
                nodes=result[0]
        else:
            new_nodes=[]
            print('nodes = ', nodes)
            for n in nodes:
                if ls:
                    result = linker(n, ls)
                    ls = result[1]
                    if type(result[0]) != list and result[0] != n:
                        new_nodes = new_nodes+[result[0]]
                    elif type(result[0]) == list:
                        new_nodes = new_nodes+result[0]
                else:
                    return Root
            nodes=new_nodes
    return Root

Согласно выставленным print в linker ('either' section) и form_tree (for-loop), при каждом запуске выводится


res ['either']
nodes =  [<__main__.node object at 0x7ffb5f0cf1d0>, <__main__.node object at 0x7ffb5f0cf940>]
nodes =  [<__main__.node object at 0x7ffb5f0cf7b8>]
res ['either']
nodes =  [<__main__.node object at 0x7ffb5f0cf8d0>, 

И выдается ответ.

Но иногда ф. form-tree (на 5 или 8 запуск)начинает бесконечно выводить:

 []
nodes =  []
nodes =  []
nodes =  []
nodes =  []
nodes =  []
nodes =  []
nodes =  []

Как бы выяснить, почему?

Используемый список

ls=[1,2,3,4,5,6,7,8,9,10,11,13,12,14,15]

print(form_tree(ls)) 

 , ,

hibiscusM ()

задачка о binary search tree / часть тестов провалено

Given the root node of a binary tree, can you determine if it's also a binary search tree?
You are not responsible for reading any input from stdin.
Hidden code stubs will assemble a binary tree and pass its root node to your function as an argument.Constraints: 0<=data<=10000

Моя функция проходит лишь 8 тестов из 14. Где здесь изъян?

def check_binary_search_tree_(root):
    if root.left or root.right: lst=[root]
    else: return 1

    while lst:
        new_list=[]
        for node in lst:
            if node.left:
                if node.data>node.left.data: new_list.append(node.left)
                else: return 0
            if node.right:
                if node.data<node.right.data: new_list.append(node.right)
                else: return 0
        lst=new_list
    return 1

 , ,

hibiscusM ()

Какие алгоритмы безопасной записи страничек B+Tree на диск вы знаете?

Есть жирный файл, в нём как-то лежат страницы килобайт по 64. Иногда надо сбросить «грязные» страницы на диск. Нельзя просто так взять и перезаписать страницу in-place: сдохнешь по середине записи и жопа тебе.

Какие вы знаете (видели в разных реализациях всяких там СУБД) способы безопасной записи таких вот страничек в файл?

Я чё-то читал про InnoDB: там в файле есть буферная зона на 128 страничек. Когда системе надо перезаписать несколько страниц, она сначала пишет их в сей буфер, делает fsync(), а потом начинает записывать страницы по своим местам. При поднятии после падения, если в буфере лежат страницы, CRC которых отличаются от CRC тех же страниц, находящихся на своих местах - значит что-то из этого буфера в прошлый раз не дописалось на свои места. Система читает страницы из буфера и дописывает их куда нужно снова. Не очень понимаю как в целом оно устроено...

Короче интересуют вот такие истории в кратком изложении про разные замуты с записью страниц на дисочку.

Читал про какие-то футеры в CouchDB, не понял почти ничего: http://guide.couchdb.org/draft/btree.html#figure/1

Я придумал такой боян:

1. Хотим записать группу страниц на диск.

2. Есть отдельный файл, растягиваемый в конец, на любое число страниц, куда мы сначала пишем все эти страницы тупо последовательно, делаем fsync.

3. В наш write ahead log пишем запись «скинуто в буфер, надо записать в большой файл».

4. Идём пишем в большой файл.

5. После записи всех страничек из буфера в «большой файл», делаем fsync, в журнал пишем «буфер вытряхнут успешно».

Но на VDS хостинге столкнулся с тем, что fsync не гарантирует, что отправленное в write() до него запишется на диск ДО того, что уйдёт во write() после него.

 

hlamotron ()

Поясните за references в Perl, мужики!

Приветствую, ЛОР!

Короче, без всякой лирики, вопрос в лоб: «Что предпочтительнее (best practice, так сказать) использовать для работы со структурами в перле: array или arrayref, hash или hashref» ?

Для себя, полагаю, что ref'ы предпочтительнее. Однако, душу гложат сомнения, ибо наверняка взятие по ссылке @$ и %$ занимает лишние такты, нежели если бы я обращался к ним напрямую $[1] или $a{mydata} соответственно.

 ,

KernelPanic ()

Ищется софт для визуализации кластеризации точек на плоскости

По сути ищется сабж.

Почему в development? Имхо, тут больше шанс встретить людей решающих подобные задачи, чем в desktop.

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

 , , , ,

pon4ik ()

drop односвязного списка на rust

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

работаю по гайду: http://cglab.ca/~abeinges/blah/too-many-lists/book/first-drop.html

мотивировка необходимости реализации drop в том, что при дефолтной реализации возможно переполнение стека при большом объеме списка. для проверки я написал тест:

    #[test]
    fn stack_overflow_on_drop() {
        let mut list = List::new();
        for n in 1..1000000 {
            list.push(n);
        }
    }

тест успешно сыплется при дефолтной реализации drop (читай: при отсутствии реализации) и успешно проходит при реализации drop, приведенной в гайде. для сравнения, приведу эту реализацию здесь:

impl Drop for List { // List - это голова списка, а не его элемент
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty); // зачищаем указатель на head
        while let Link::More(mut boxed) = cur_link {
            cur_link = mem::replace(&mut boxed.next, Link::Empty); // зачищаем указатель на каждый next
        }
    }
}

теперь моя реализация:

impl Drop for List { // List - это голова списка, а не его элемент
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty); // зачищаем указатель на head
        while let Link::More(boxed) = cur_link {
            cur_link = boxed.next; // проходим по списку, но ничего не зачищаем
        }
    }
}

вопрос: почему эта реализация не переполняет стек при освобождении списка (проходит тест)? является ли она корректной, или это случайность?

 , ,

MyTrooName ()

Словарь алгоритмов и структур данных от NIST

В букмарки:

https://xlinux.nist.gov/dads/

 , , , ,

Oxdeadbeef ()

Javascript вытащить свойста объекта (со вложенными объектами) в массив

Всем привет!

Кто в алгоритмах шарит кто? Подскажите, пожалуйста, как вытащить ключи объекта, который может содержать в себе объекты бесконечной вложенности, в массив.

Например, если есть объект:

var obj = {
    field_1: 'value 1',
    field_2: {
        ffield_1: {fffield_1: 1}
    }

На выходе должен получиться массив:

['field_1', 'field_2', 'ffield_1', 'fffield_1']

 , ,

djnoob ()

Очень продвинутая записная книжка

Суть токова: необходима система типа жуйка, бнв или поинта, только чтобы была на моём локалхосте (ну или впске) и умела в поиск по нескольким тегам. То есть я пложу кучу записей, раза в три меньшую кучу тегов и мне надо впоследствии смотреть теги у записей и по нескольким тегам вычленять подходящие записи.
Юзкейс: у меня куча объектов, и надо как-то учитывать все работы на них, всё аппаратное обеспечение и всякие сведения типа координат/адресов/паролей/ответственных. Собственно, такая база данных поможет мне даже спустя пару лет выяснить многое, за чем необходимо съездить посмотреть, но не отрывая жопы от стула.

 , , ,

kostett ()

Хранение метаданных в многомерном массиве

В результате обработки экспериментальных данных получаю многомерный массив значений при разных параметрах эксперимента. Эти данные впоследствие используются для отображения различных зависимостей. Все эксперименты разные и в каждом из них варьируется свой набор параметров(например, в одном эксперименте варьируется температура и мощность лазерного излучения при заданном напряжении и длине зазора, а в другом наоборот длина зазора и напряжение при заданной температуре и мощности лазерного излучения). В данный момент использую многомерный массив, но каждый раз приходится смотреть как записаны данные; для каждого эксперимента приходится писать много дублирующегося кода. Интересно есть ли какой-то универсальный способ хранения данных, который бы включал в себя метаданные эксперимента? Язык программирования python

 ,

gameover__ ()

Java datastructures

Интересно, почему в java нет такой очевидной и часто нужной структуры данных как упорядоченная коллекция ключ-значение с поддержкой дубликатов ключей.

Или оно все же есть в стандартной библиотеке, а я ее не заметил?

 , ,

unt1tled ()

Библиотека алгоритмов и структур данных для C

В который раз наблюдая за велосипедами в одном сишном проекте, задался вопросом, а нет ли относительно «стандартной» библиотеки для алгоритмов и структур данных, хотя бы на уровне крестовой STL?

И даже если есть, то почему почти в каждом проекте(возьмем для простоты открытые) свои велосипеды? На каждый чих. Неужели язык толкает на это(сложно предложить достаточно общее решение)?

Если такой библиотеки просто нет, то возможно есть смысл ее создать? У кого какие мысли, кто какие перспективные разработки знает?

И да, я в курсе существования glibc, queue.h и tree.h, коллекций в glib и пр.

Есть еще какие-то sglib, gdsl. Но их не использовал и их использование не видел.

 , ,

forCe ()

Приложения DSU

Кто что посоветует почитать по сабжу?

 

pon4ik ()

Пользовательские структуры данных в Clojure

Подскажите, пожалуйста, можно ли в Clojure создавать свои структуры данных? (например декартово дерево по неявному ключу) Проигрывают ли они при этом в эффективности другим хардкорным языка программирования (типа Си, С++ где можно оперировать данными на стеке и т.п.)?

 , ,

elf80lvl ()

Дерево с быстрым доставанием родителей ноды

Дерево произвольного количества нод на каждой ветке. Допустим, у каждой ноды есть какой-то набор какого-то добра, т.е. добро ноды на уровне k + 1 состоит из ее добра и добра всех ее предков.

Еще нужно эту структуру хранить как какую-то персистентнуюю опердень, но нет условия на конкретную реализацию - т.е., если будет удобно в mysql, то mysql, если имеется какое-то дерево, которое может быть персистентным, было бы отлично. Еще (опционально) было бы неплохо иметь возможность шардить.

Важно вот что - в любой предложенной реализации должна присутствовать возможность получить для ноды список всех предков при уловии, что у каждой ноды один родитель, что очевидно, до корня. (банально записать просто плоской структурой в sql не катит, ибо если у дерева высота 1к, то это 1к запросов - ну его). И второй ключевой момент - оязательна возможность перекидывать ноды (как по соседству, так и с уровня на уровень), и чтоб при этом их добро менялось в соответствии с новым положением, в т.ч. и добро их детей.

(добавил в теги «математика», ибо математики обычно и подстказывают годные идеи, но если вас зацепило - простите)

 , , , математика.,

cdshines ()

Оптимальный формат хранения данных

disclaimer

скорее всего мне никогда это не пригодится, но хочется узнать мнение умных людей

допустим у меня есть матрица с 450’000’000 строчек и 8 столбиков. в ней хранятся значения типа «float» (значения плавают в диапазоне -36 — 36, и есть 7 знаков после точки). нужно это сбросить на диск и чтобы это занимало как можна меньше места..

update: Особенно интересно можна все это поместить в 16Гб флеху (реально там 14.9Гб места если я нигде не ошибся)

 , ,

ZuBB ()