Ostrovok.ru corporate blog
July 2011 22

Итоги конкурса. часть 2: Бэкендеры

Привет, Хаброжители!

Продолжая тему, в этом посте мы подведём итоги конкурса для бэкенд-разработчиков, расскажем о типичных ошибках и хороших решениях вопросов.

Конкурс состоял из восьми заданий, проверяющих знания Python и сопутствующих технологий.



Вопрос 1. Какие есть методы организации параллельных вычислений, какие преимущества и недостатки у каждого метода?

Нам приходили целые трактаты о том, какие существуют способы разделения вычислений, что, собственно, не удивительно — проблема очень актуальная в современном мире. В ответе на этот вопрос достаточно было упомянуть два основных способа:
  • Параллельность на уровне потоков
    Все, кто прошли тест, прекрасно представляют себе, как проводятся вычисления в параллельных потоках. Но не многие указали, что знают, что такое GIL (Global Interpreter Lock, такой метод блокировки тормозит выполнение всех потоков кроме того, что установил блокировку). И, да, было бы круто упомянуть coroutine-фреймворки, которые позволяют обойти GIL, но они довольно сложны в применении и не решают проблем, связанных с синхронизацией IO. Кстати о последнем — есть библиотеки, которые позволяют выполнять асинхронное IO, например в состав twisted входит пакет twisted.internet.fdesc, но применение этих фреймворков довольно трудозатратно.
  • Параллельность на уровне процессов
    Такой подход позволяет лучше использовать мощности процессора, не чувствителен к GIL, однако синхронизация процессов всё ещё представляет некоторые сложности.


Вопрос 2. Оцените сложность алгоритма и предложите варианты по улучшению

def uniq(iterable):
	result = []
	for i in interable:
		if i not in result:
			result.append(i)
	return result


На самом деле, большиство ответивших ошиблись с расчётом сложности.
		if i not in result:

Так как result является списком, то сложность этой операции O(n), где n — длина result. А длина result с каждой итерацией по iterable изменяется от 1 до n. Мы имеем арифметическую прогрессию, а, значит, сложность будет — O(n^2).

Чтобы улучшить, необходимо поменять структуру данных. Тип set на вставку имеет сложность O(1) и на поиск внутри себя тоже O(1) (если интересно больше, читайте про временную сложность).

Можно переписать так:
def uniq(iterable):
	result = set()
	for i in interable:
		if i not in result:
			result.append(i)
	return list(result)
и сложность станет линейной.

Но круче:
def uniq(iterable):
	result = list(set(iterable))


Вопрос 3. В чём разница и почему так?

r = range(3)

a = r * 2
print a # [0, 1, 2, 0, 1, 2]
a[0] = 1
print a # [1, 1, 2, 0, 1, 2]

a = [r] * 2
print a # [[0, 1, 2], [0, 1, 2]]
a[0][0] = 1
print a # [[1, 1, 2], [1, 1, 2]]


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

Специфика оператора умножения, применённого к списку, такова — он повторяет list используя shallow copy.

То есть допустимо переписать выражения:
a = z + z # a = r * 2
""" это конкатенация двух листов, все числа копируются в новый общий лист """

a = [z] + [z] # a = [z] * 2
""" в данном случае копируются ссылки """

Это и создаёт описанный в вопросе эффект.

Вопрос 4. Мы придумали свой класс Point для хранения координат и примитивных операций над ними

Выглядит он примерно так:
class Point(): 
	def __init__(self): 
  		self.a = None
		self.b = None
		self.c = None
		...


Потом обнаружили, что программа, оперирующая большим количеством экземпляров такого класса ест много памяти. Миллион таких объектов занимает минимум 360мб. Что занимает так много памяти и как можно улучшить ситуацию?

Этот вопрос доставил наибольшее количество хлопот участникам. Самый корректный способ — это использовать свойство __slots__, где нужно перечислить названия всех полей, это сильно сократит размер объекта.

class Point(object):
	__slots__=('a', 'b', 'c')
	def __init__(self): 
		self.a = None
		self.b = None
		self.c = None


Есть также альтернативный вариант решения: заменить класс Point на tuple.

Вопрос 5. Что происходит? Кто виноват? Что делать?

def add1Cent(sum):
	return sum + 0.01

s = 0

for i in range(5):
	s = add1Cent(s)
""" now I have 5 cents! """

print s == 0.05 # True
""" ok, lets add another five! """

for i in range(5):
	s = add1Cent(s)
""" now I have 10! """

print s == 0.1 # False
print s > 0.1 # False
print s < 0.1 # True

Этот вопрос очень простой, и никто не допустил в нём ошибки.

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

Вопрос 6. Перепишите следующий код с использованием генераторов

file = open('somefile.csv')
total = 0
for line in file:
	csv_list = line.split(',')
	if csv_list[5]:
		 total += int(csv_list[5])

print "Всего: ", total

Какие плюсы у получившегося кода? Какие минусы?

Это задание не создало трудностей. Переписать этот код можно сотней способов, мы ждали чего-то вроде:
total = sum(int(line.split(',')[5]) for line in open('somefile.csv') if line.split(',')[5])

Плюсы: мало кода.
Минусы: нечитаемо, 30% падение производительности.

Вопрос 7. В чем разница между 'фыва' и u'фыва'? Где и почему это важно?

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

'фыва' # строка закодированная по-умолчанию.

Все строки в python по умолчанию кодируются в ASCII (именно поэтому при компиляции возникает проблема, если строка сожержит не ASCII символ). Такое поведение можно изменить, декларировав кодировку в заголовке файла, написав в первой строке, например “# coding=utf-8”, тогда все строки будут восприниматься как закодированные в UTF-8.

u'фыва' # строка закодированная в unicode.

Строка в кодировке Unicode. Эта кодировка поддерживает все существующие языки и символы. Выгода, применения такой кодировки, для работы с данными очевидна. Например, для многоязычных приложений.

Некоторые функции python конвертируют строки в кодировку указанную по умолчанию, например print().

Работа с cvs и xml библиотеками невозможна без качественного понимания различий этих типов данных.

Вопрос 8. Как переписать код, чтобы в конструкторе B запускался и конструктор класса A

class A:
	def __init__(self):
		print "init in A"

class B(A):
	def __init__(self):
		print "init in B"

b = B() # init in B

С этим вопросом справилось абсолютное большинство. Так что просто отметим тот факт, что крутой ответ содержал два примера: для new style objects и old style.

Лучший из бэкендеров

Сегодня к нам в гости приходил Максим Аванов ghostwriter, мы провели ему экскурсию по офису и познакомили с членами команды. Максим ехал к нам на поезде аж 14 часов из города Чебоксары, где, как он рассказал, делает свой медиа-ресурс про компьютерные игры, которые хочет продвинуть на зарубежный рынок.

Максим Аванов, ghostwriter

Максим об Островке и стартапах:
Здорово, что есть люди, которые видят смысл в том, чтобы серьезно подходить к делу.
Мода на стартапы и погоня за инвесторскими деньгами — это как-то нездорово.
Нужно заниматься, тем что любишь и во что веришь.


Спасибо всем, кто принял участие!


Команда Островок.ru

P.S.: Следующий пост будет посвящен аналитикам.
P.P.S.: Кстати, у нас есть вакансии для python-разработчиков!
+11
6k 25
Comments 25
Top of the day