Рубрика «деревья» - 2

image

Помню, в детстве, когда попадал в лес, задавался вопросом: «А сколько же в лесу деревьев?» Посчитать их мне не удалось, но думаю, что лесозаготавливающие компании должны как-то прикидывать количество деревьев на участке – например, умножить среднюю плотность на площадь.

Посчитать количество деревьев в большой стране – на порядок сложнее, а во всём мире – и того тяжелее, ведь плотность разных лесов разная, и даже лучшие спутниковые фотографии покажут вам только зелёные ковры из листьев. Конечно, спутниковые снимки всё равно помогали учёным примерно оценивать богатства нашей планеты. Например, количество деревьев на всей Земле до недавнего времени по этим снимкам оценивалось в 400 миллиардов.

image

Но недавно учёные из университетов и институтов 15 стран (в том числе и российские учёные из Центра по проблемам экологии и продуктивности лесов РАН) под руководством эколога Томаса Кроутера (Thomas Crowther) закончили большую работу по обработке огромного количества данных со всех уголков планеты по поводу реальной плотности лесов в разных её частях. Плотность лесов подсчитывалась просто — вручную. Этим занимались различные экологические институты и организации, и выкладывали результаты работы в интернет.

В результате учёные получили первую глобальную подробную карту лесов, учитывающую не только площадь покрытой лесом земли, но и данные по плотности зарослей. Оказалось, что деревьев на планете почти в 8 раз больше, чем считалось раньше: около 3 040 000 000 000, или чуть более 3 триллионов.
Читать полностью »

Что будет, если каждому дереву выдать email - 1

В 2013 году власти Мельбурна провели каталогизацию всех 70 000 городских деревьев (см. карту всех деревьев). Каждому из них присвоили персональный ID и соответствующий почтовый адрес. По задумке, так горожанам будет проще оперативно сообщать о возможных проблемах, вроде опасно свисающих ветвей.
Читать полностью »

image

Моя статья про стартап BioCarbon Engineering, предлагающий приспособить для масштабной высадки деревьев беспилотные летательные аппараты, вызвала интерес читателей и породила многие вопросы. Напомню, что эта компания планирует высаживать по миллиарду деревьев в год.

Для высадки планируется использовать коптеры, которые будут разбрасывать капсулы, содержащие пророщенные семена деревьев. Высадка будет происходить на заранее размеченной и картографированной территории. По оценкам компании, два оператора дронов за день смогут высадить до 36000 деревьев. При этом стоимость работы составит не более 15% от стоимости посадки обычными методами.
Читать полностью »

image

Стартап BioCarbon Engineering предлагает, пожалуй, лучший и наиболее естественный способ борьбы с избытком углекислоты в атмосфере – масштабное высаживание лесов. Но вместо весёлых субботников с привлечением населения, изобретатели хотят приспособить для этого технологии 21 века – беспилотные летательные аппараты.

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

По прикидкам продовольственной и сельскохозяйственной организации ООН, в 21 веке ежегодно на планете вырубают по 6 миллионов га. Это чуть больше площади Московской области. По их же оценкам, количество вырубаемых ежегодно деревьев составляет примерно 26 миллиардов, а новых посадок производится всего 15 миллиардов. Кстати, Россия занимает первое место в мире по скорости вырубки лесов – на её долю приходится почти половина добычи древесины.
Читать полностью »

Яндекс.Диск — один из немногих сервисов Яндекса, частью которого является программное обеспечение для десктопа. И одна из самых важных его составляющих — алгоритм синхронизации локальных файлов с их копией в облаке. Недавно нам пришлось его полностью поменять. Если старая версия с трудом переваривала даже несколько десятков тысяч файлов и к тому же не достаточно быстро реагировала на некоторые «сложные» действия пользователя, то новая, используя те же ресурсы, справляется с сотнями тысяч файлов.

В этом посте я расскажу, почему так получилось: чего мы не смогли предвидеть, когда придумывали первую версию ПО Яндекс.Диска, и как создавали новую.

Новый алгоритм синхронизации Яндекс.Диска: как не подавиться 900 000 файлов - 1

Прежде всего, о самой задаче синхронизации. Технически говоря, она состоит в том, чтобы в папке Яндекс.Диска на компьютере пользователя и в облаке был один и тот же набор файлов. То есть такие действия пользователя, как переименование, удаление, копирование, добавление и изменение файлов, должны синхронизироваться с облаком автоматически.
Читать полностью »

Очередной пост в рамках нашего цикла лекций Технопарка. В этот раз мы предлагаем вашему вниманию курс, посвящённый алгоритмам и структурам данных. Автор курса — Степан Мацкевич, сотрудник компании ABBYY.

Лекция 1. Основы

Начало первой лекции посвящено обсуждению основных понятий, на которых строится вся дальнейшая программа курса: что такое алгоритм и структура данных. Описаны базовые виды алгоритмов, их характеристики и методы анализа. Далее рассматриваются примеры создания алгоритмов для вычисления чисел Фибоначчи, проверки числа на простоту, быстрого возведения числа в целую степень. В конце лекции рассказывается об особенностях использования алгоритмов для работы с массивами: создание однопроходных алгоритмов, поиск минимального элемента, бинарный поиск.


Читать полностью »

Оригинал на английском dmitra.com/graphiy/general-purpose-tree-editor/

Начиналось все с простой потребности в наведении порядка в файлах. Почему уже 2014 год, а до сих пор нет простого и удобного редактора деревьев хотя бы?
Текстовых редакторов — несметное множество и все равно появляются новые. Редакторов таблиц — поменьше, но жаловаться приходится только когда количество данных исчисляется тысячами.
А ведь самих-то способов представления информации не так много:
Строка, Список, Таблица, График, Диаграмма, Карта, 3d
Разумеется, есть огромное множество разновидностей этих видов, но количество достаточно популярных не превышает десятка.
По своей сути эти способы можно подразделить по количеству одновременно отображаемых характеристик.
Одномерные: список, временная шкала, хронометраж и т.п.
Двумерные: таблица, карта, график, гистрограмма и т.п.
Трехмерные: в основном нестандартные сложные научные 3d-визуализации
Многомерные: деревья, графы, сети

Визуализаций данных уже создано в избытке и продолжают изобретать новые. Для одних только деревьев известно под 3 сотни вариантов: treevis.net
А вот редакторы существуют для весьма малого количества самых популярных.
И в отношении многомерных данных существует огромный пробел.
Читать полностью »

Очень часто за основу архитектуры приложения берётся дерево. Простой пример: есть страны, в странах — области, в областях — города, в городах — организации, в организациях — работники, товары или что-либо ещё. Использование дерева вполне логично и оправдано. Иерархичность такой системы показывает некая абстрактная таблица. Назовём её object:

CREATE TABLE object (
  id NUMBER(11),
  parent_id NUMBER(11),
  type VARCHAR2(16) NOT NULL,
  name VARCHAR2(255) NOT NULL,
  CONSTRAINT pk_object PRIMARY KEY (id),
  CONSTRAINT fk_object_parent FOREIGN KEY (parent_id) REFERENCES object (id) ON DELETE CASCADE ENABLE
);

Наполним её какими-нибудь данными:

id  |  parent_id  |  type     |  name
------------------------------------------------------
1   |  NULL       |  country  |  Россия
2   |  1          |  region   |  Московская область
3   |  1          |  region   |  Новосибирская область
4   |  2          |  city     |  Москва
5   |  3          |  city     |  Новосибирск

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

-- Выбрать все города России
SELECT *
  FROM object
    WHERE type = 'city'
    START WITH id = 1 CONNECT BY PRIOR id = parent_id;

-- Выбрать страну, в которой находится Новосибирск
SELECT *
  FROM object
    WHERE type = 'country'
    START WITH id = 5 CONNECT BY PRIOR parent_id = id;

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

Здравствуй Хабр!
Сегодня я хочу рассказать о генерации деревьев на HTML5 Canvas с помощью JavaScript. Сразу поясню, что речь идет не о деревьях ссылок или B-дереьях, а о тех деревья, которые мы каждый день видим у себя за окном, тех, которые делают наш воздух чище и богаче кислородом, тех, что желтеют осенью и теряют листья зимой, вообщем о тех самых живых, лесных, настоящих деревьях, только нарисованных на Canvas и пойдет речь.

Генерация деревьев на HTML5 Canvas
Такие вот деревья получаются

Генерация деревьев нужна была мне для моей игры. Но некаких адекватных алгоритмов мне найти так и не удалось. Поэтому я написал свой генератор…
Не хочу ничего читать, хочу сразу результат!
Читать полностью »

Здравствуйте.

Меня зовут Александр Рулёв и я хочу рассказать вам о структуре данных, на которую я совершенно случайно наткнулся (на самом деле около трёх дней перебирал возможные комбинации, пока не получил что-то однозначное).

У меня просто была проблема, которая оказалась не проблемой в реальном мире, но кажется я решил её в мире абстрактном.

Проблема была следующая: есть список элементов определённой длины. Мы должны быстро получать элемент по индексу, а так же иметь возможность вставить/удалить с любой позиции элемент. Причём чтобы остальные «пододвинулись», либо схлопнулись. Очевидно, что ни линейный список, ни массив не подходят. А обычное дерево не имеет возможности получить элемент по индексу без обхода дерева, которое тоже O(N) и лучше мы бы использовали список.

И кажется я решил эту проблему. И в данный момент это что-то похожее на эйфорию, поскольку находится всё больше и больше вариантов применения придуманной структуры данных, а фундаментальных проблем всё ещё не видно.

Асимптоматика свойственная дереву: O(log N) на все операции. Вставка/удаление в наивной реализации O((log N)^2), но мне кажется, что это можно оптимизировать.

В этой статье (первой, надеюсь не последней) я опишу, что представляет из себя это дерево, а так же как совершать над ним операции. Если всё работает так, как мне кажется и вы не найдёте никаких проблем, которые нельзя починить — мир получает прекрасную (как мне кажется) структуру данных. Иначе мне будет стыдно.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js