Задачи решаемые способом замены данных

Обмен значений переменных: разбор популярных способов решения известной задачи с IT-собеседований

Авторизуйтесь

Обмен значений переменных: разбор популярных способов решения известной задачи с IT-собеседований

Самый простой способ взаимно менять значения переменных — использование swap(a, b) или же аналогичного стандартного метода. Тем не менее, важно понимать как работает операция по обмену значений двух переменных, что мы покажем на нескольких примерах.

Для начала продемонстрируем неправильную реализацию и выясним, что в ней не так.

Ошибочная реализация

Если вы попытаетесь выполнить обмен значений этим способом, то увидите, что теперь в обеих переменных хранится значение переменной b . Происходит это ввиду построчного выполнения кода. Первая операция присваивания сохраняет значение переменной b в переменную a . Затем вторая — новое значение a в b , иными словами значение b в b . Таким образом, мы полностью теряем содержание контейнера a .

Теперь обратимся к правильной реализации.

С использованием буфера

Буфером в данном случае называется дополнительная используемая память. Давайте разберёмся зачем она здесь нужна. Если помните, в неправильной реализации мы потеряли значение переменной a после первой операции присваивания, в связи с чем в обеих доступных переменных осталось значение b . Чтобы этого избежать нам понадобится ещё одна переменная — c . В таком случае правильный алгоритм будет выглядеть так:

Для наглядности разберём его пошагово:

1. Присваиваем переменной c значение переменной a . Сейчас в a записана a , в b — b , а в c — a .
2. Присваиваем переменной a значение переменной b . Теперь в a хранится b , в b — также b и в c — a .
3. Присваиваем переменной b значение переменной c . Сейчас в a находится старое значение b , в b — a , ну и в c остаётся a .

Как вы видите, переменная c после выполнения алгоритма не нужна, поэтому далee в программе её можно не использовать и даже вовсе удалить из памяти.

Сразу стоит заметить, что это самое краткое и экономное решение задачи, но можно использовать и больше переменных, не так ли?

Нам повезло, что сейчас вопрос экономии оперативной памяти не стоит так остро, как 20-30 лет назад. Тем не менее, в те времена swap был востребован не меньше, поэтому умные люди нашли способ заменить значения двух переменных без ввода третьей.

Арифметика

Сложение / вычитание

Для лучшего восприятия снова разберём алгоритм построчно:

1. Присваиваем переменной a сумму значений переменных a и b . Сeйчас в a записано значение a + b , а в b всё ещё b .
2. Переменной b присваиваем разность между новым значением переменной a и переменной b . В a также хранится a + b , но в b уже a .
3. Наконец, присваиваем переменной a результат вычитания b из обновлённого значения a . Получается, что в a теперь содержится b , а в b — a .

Для C-подобных языков сокращённая запись этого алгоритма выглядит так:

Умножение / деление

Аналогичный способ решения задачи получается при замене сложения умножением и вычитания делением:

В сокращённом варианте:

Вычитание / Сложение

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

Обратите внимание, что в последней строке знак у переменной a изменился, а саму строчку можно записать иначе: a = b — a; .

Такой же принцип можно использовать поменяв местами деление и умножение.

Недостатки арифметического метода

Главным недостатком является большее количество операций, в чём можно убедиться посчитав операции сложения, вычитания и присваивания. Тeм болee, что умножeниe и дeлeниe болee «дорогостящиe». Заметной потеря скорости становится в ситуации, когда трeбуeтся менять значения большого количества пeрeмeнных.

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

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

Битовые операции

Данный алгоритм основан на следующем свойстве операции XOR («исключающее или»): a XOR b XOR a = b .

Для любитeлeй коротких записeй приведём код одной строчкой. XOR в C-подобных языках замeняeтся знаком ^ :

Однако помните о точках следования. Из-за них этот код может вести себя непредсказуемо и давать разные результаты, поэтому никогда не используйте его в production коде.

Обязательно посмотрите более подробный разбор решения через битовые операции от Г. Лакмана Макдауэлла, автора известного сборника задач с собеседований, который есть в одной из наших книжных подборок.

Источник

Нестандартные задачи для начальных классов (замена данных, переливание)

Задачи на замену данных

Задачи на переливание

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

• Сейчас обучается 798 человек из 78 регионов

Курс повышения квалификации

Специфика преподавания предмета «Родной (русский) язык» с учетом реализации ФГОС НОО

• Сейчас обучается 306 человек из 59 регионов

Курс повышения квалификации

Скоростное чтение

• Сейчас обучается 623 человека из 79 регионов

Ищем педагогов в команду «Инфоурок»

Номер материала: ДБ-397223

Международная дистанционная олимпиада Осень 2021

Не нашли то что искали?

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Безлимитный доступ к занятиям с онлайн-репетиторами

Выгоднее, чем оплачивать каждое занятие отдельно

В Осетии студенты проведут уроки вместо учителей старше 60 лет

Время чтения: 1 минута

Минпросвещения разрабатывает образовательный минимум для подготовки педагогов

Время чтения: 2 минуты

Учителям предлагают 1,5 миллиона рублей за переезд в Златоуст

Время чтения: 1 минута

На новом «Уроке цифры» школьникам расскажут о разработке игр

Время чтения: 1 минута

Минобрнауки учредит именные стипендии для студентов из малочисленных народов

Время чтения: 1 минута

Российские адвокаты бесплатно проконсультируют детей 19 ноября

Время чтения: 2 минуты

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Источник

Предварительная обработка данных

Всем привет! Я веб-разработчик и вот уже несколько лет интересуюсь машинным обучением. Поскольку в повседневной рабочей парктике мне приходится решать менее интересные для меня задачи, не связанные с машинным обучением, время от времени я забываю то, о чем когда-то читал или использовал. Чтобы составить памятку для себя, укрепить свои знания и поделиться ими с окружающими, я решил написать несколько статей по машинному обучению. Начну с предварительной обработки данных.

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

Пропуски

Рассмотрим набор данных следующего вида. Я его честно придумал и далее в рамках этой статьи буду ссылаться на него.

ID	Имя	Спортивная дисциплина	Страна	Год рождения спортсмена	Вес спортсмена	Медаль
1	Иван	Академическая гребля	Российская Федерация	1985	265	B
2	Бокс	Великобритания	1986	54	S
3	Ким	Греко-римская борьба	Северная Корея	1986	93	G
4	Олег	Греко-римская борьба	1984	B
5	Педро	Академическая гребля	Бразилия	97	N
6	Валерий	Академическая гребля	Российская Федерация	2004	97	N

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

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

Категориальный признак — признак, значение которого можно отнести к какой-либо группе, но порядок значений в этой группе абсолютно не важен. Более того, между значениями категориальных признаков невозможно установить отношения «больше» или «меньше». Однако, никто не мешает исследователю отсортировать значения признака, например, по алфавиту для наглядности или по какому-либо другому критерию для какой-либо другой цели. Примеры категориальных признаков в моем наборе данных: Имя, Спортивная дисциплина, Страна, Год рождения спортсмена.

Значения численного признака является скаляром. Объекты в наборе данных можно упорядочить по значению такого признака в возрастающем или убывающем порядке. В качестве примеров численного признака можно привести Год рождения спортсмена и Вес спортсмена.

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

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

Заполнить пропуски в категориальных признаках можно следующими способами:

• Заменить пропущенное значение новой категорией «Неизвестно».

ID	Имя	Спортивная дисциплина	Страна	Год рождения спортсмена	Вес спортсмена	Медаль
2	Неизвестно	Бокс	Великобритания	1986	54	S

ID	Имя	Спортивная дисциплина	Страна	Год рождения спортсмена	Вес спортсмена	Медаль
4	Олег	Греко-римская борьба	Российская Федерация	1984	B

Пропуски в численных признаках

Если имеем дело с численными признаками, можно применить следующие подходы:

• Заменить пропущенное значение средним значением.

ID	Имя	Спортивная дисциплина	Страна	Год рождения спортсмена	Вес спортсмена	Медаль
4	Олег	Греко-римская борьба	1984	(265 + 54 + 93 + 97 + 97) / 5 = 121.2	B

Как видно из примера выше, выброс значения признака «Вес спортсмена» в строке с идентификатором 1 очень сильно повлиял на среднее значение.

• Заменить пропущенное значение медианой. Если в данных присутствуют выбросы, этот способ замены пропусков является предпочтительным.

ID	Имя	Спортивная дисциплина	Страна	Год рождения спортсмена	Вес спортсмена	Медаль
4	Олег	Греко-римская борьба	1984	Медиана(54, 93, 97, 97, 265) = 97	B

Выбросы

В данных могут присутствовать значения, являющиеся выбросами. Это, как правило, не ошибки. Однако, своими значениями они «шокируют» модель. Пример выброса — значение веса Ивана из таблицы выше (ниже продублирована строка).

ID	Имя	Спортивная дисциплина	Страна	Год рождения спортсмена	Вес спортсмена	Медаль
1	Иван	Академическая гребля	Российская Федерация	1985	265	B

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

где — первая квартиль — такое значение признака, меньше которого ровно 25% всех значений признаков. — третья квартиль — значение, меньше которого ровно 75% всех значений признака.

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

Чаще всего от выбросов в обучающей выборке лучше всего избавляться.

Нормализация

Нормализация — это приведение всех значений признака к новому диапазону. Например, к диапазону [0, 1]. Это полезно, поскольку значения признаков могут изменяться в очень большом диапазоне. Причем, значения разных признаков могут отличаться на несколько порядков. А после нормализации они все будут находиться в узком (и, часто, едином) диапазоне.

Наиболее популярным способом нормализации является нормализация методом минимакса. Для того, чтобы применить этот метод, должно быть известно максимальное и минимальное значение признака. Проблема в том, что эти значения известны не всегда.

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

где — среднеквадратическое отклонение признака X.

Выполняется Z-нормализация по формуле ниже.

где M[X] — математическое ожидание признака X.

Отмечу, что в случае применения Z-нормализации к нескольким признакам, диапазон значений для них будет разным.

One-hot encoding

Это способ предварительной обработки категориальных признаков. Многие модели плохо работают с категориальными признаками как таковыми. Дело в том, что слово «Российская Федерация» нельзя просто взять и умножить на какое-нибудь число. Но многие модели работают именно так: берется коэффициент и на него умножается значение признака. Аналогичная операция выполняется с остальными признаками. Все результаты суммируются. На основе значения суммы делается вывод о принадлежности объекта к тому или иному классу (такие модели называются линейными).

Однако, как поступать с признаками, значения которых нельзя выразить численно? Можно заменить их значения численным идентификатором. Например, вместо значения «Российская Федерация» использовать значение 1, а вместо «Великобритания» — 2. Тогда линейная модель будет работать. Но, если поступить таким образом, будет утеряно свойство категориальности признака. Иными словами, модель будет пытаться сравнивать идентификаторы признаков между собой. Но они не сравнимы по значению.

Чтобы бороться с этой проблемой, был придуман способ преобразовать исходный признак в несколько новых, бинарных признаков. Например, можно признак «Страна» превратить в 4 новых бинарных признака следующим образом:

ID	Имя	Страна_Российская Федерация	Страна_Великобритания	Страна_Северная Корея	Страна_Бразилия
1	Иван	1	0	0	0
2	Майкл	0	1	0	0
3	Ким	0	0	0	1	0
4	Олег	1	0	0	0
5	Педро	0	0	0	1
6	Валерий	1	0	0	0

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

Заключение

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

Спасибо, что дочитал или долистал до сюда. Я описал далеко не все способы предварительной обработки, да и эта статья вряд ли пригодится профессиональным data scientist-ам. Однако, если ты новичок и не знаешь что делать со своими данными, можешь смело сюда возвращаться. Удачи в обучении и интересных задач!

Список источников

Я не ученый и эта статья не претендует на звание научной. Поэтому и источники я не буду оформлять по ГОСТам. Прошу за это меня извинить.

Источник