Вы когда-нибудь программировали, слушали песни в фоновом режиме и ломали их, когда вдруг
Test failed: Expected ligma got balls, lol have fun figuring this one out bud
То же самое произошло со мной, когда я работал над задачей LeetCode Минимум топлива для отчета в капитал. Это довольно стандартная задача с графом, в которой используется DFS/BFS, и я уже решил эту проблему на Rust, C и Java, поэтому решил переписать ее на Python, потому что, очевидно, это следующий шаг, когда вы решите проблему в 3. разные языки — решить задачу на четвертом языке.
Итак, я, по сути, выполнил индивидуальный перевод моего кода Rust на Python и…
Посмотрите мой код на Rust и Python и посмотрите, сможете ли вы обнаружить ошибку.
impl Solution {
pub fn minimum_fuel_cost(roads: Vec<Vec<i32>>, seats: i32) -> i64 {
const CAPITAL : usize = 0;
let num_of_cities: usize = roads.len() + 1;
let seats: i64 = i64::from(seats);
let mut adj_list : Vec<Vec<usize>> = vec![Vec::with_capacity(num_of_cities); num_of_cities];
for road in roads {
adj_list[road[0] as usize].push(road[1] as usize);
adj_list[road[1] as usize].push(road[0] as usize);
}
let mut distances: Vec<u32> = vec![0; num_of_cities];
let mut frontier: Vec<(usize, u32)> = vec![(CAPITAL, 0)];
let mut visited: Vec<bool> = vec![false; num_of_cities];
while let Some((city, dist)) = frontier.pop() {
distances[city] = dist;
visited[city] = true;
for &neighbor in adj_list[city].iter() {
if !visited[neighbor] {
frontier.push((neighbor, dist + 1));
}
}
}
let mut frontier : Vec<usize> = (0..num_of_cities).collect();
let mut people_count : Vec<i64> = vec![1; num_of_cities];
frontier.sort_unstable_by_key(|&city| distances[city]);
while let Some(city) = frontier.pop() {
for &neighbor in adj_list[city].iter() {
if distances[neighbor] < distances[city] {
people_count[neighbor] += people_count[city];
break;
}
}
}
let car_count : Vec<i64> = people_count
.into_iter()
.map(|count| count / seats + if count % seats == 0 {0} else {1})
.collect();
let capital_count = car_count[CAPITAL];
car_count.into_iter().sum::<i64>() - capital_count
}
}
class Solution:
def __init__(self):
self._CAPITAL = 0
def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
number_of_cities: int = len(roads) + 1
adj_list: List[List[int]] = [[]] * number_of_cities
for road in roads:
adj_list[road[0]].append(road[1])
adj_list[road[1]].append(road[0])
distances: List[int] = [0] * number_of_cities
frontier: List[Tuple[int, int]] = [(self._CAPITAL, 0)]
visited: List[bool] = [False] * number_of_cities
while frontier:
city, distance = frontier.pop(-1)
distances[city] = distance
visited[city] = True
for neighbor in adj_list[city] :
if not visited[neighbor]:
frontier.append((neighbor, distance + 1))
frontier: List[int] = sorted(range(number_of_cities), key = lambda city : distances[city])
people_count: List[int] = [1] * number_of_cities
while frontier:
city = frontier.pop()
for neighbor in adj_list[city]:
if distances[neighbor] < distances[city] :
people_count[neighbor] += people_count[city]
break
people_count.pop(0)
car_count: List[int] = [(count // seats) + (1 if count % seats != 0 else 0) for count in people_count]
return sum(car_count)
Вы видите это? Если нет, я дам тебе строку, посмотрим, сможешь ли ты найти ее с помощью нее.
Проблема в следующей строке:
adj_list = [[]] * number_of_cities
Все еще нет? Позвольте мне показать вам, что происходит, и посмотрим, сможете ли вы тогда разобраться в проблеме.
Посмотрите на следующий фрагмент Python:
mat = [[0] * 3] * 4 mat[0][0] = 1 print(mat)
Давайте посмотрим вывод фрагмента
Сможете ли вы разобраться в проблеме сейчас?
Если это все еще не очевидно, проблема в том, что `[x] * 4` в Python создает 4 поверхностные копии x и сохраняет их в списке, это по сути эквивалентно написанию `[x, x, x, x]`. Поскольку он создает мелкие копии, а список в Python является изменяемым, он в основном создает 4 точки доступа для одного и того же значения списка, вместо того, чтобы иметь разные списки соседей для каждого узла, у меня был один и тот же список.
Теперь вы, возможно, думаете про себя: «О, это простая ошибка, которую нужно выяснить». Мне потребовалось более 3 часов, чтобы разобраться в этой проблеме. Для контекста мне потребовалось около получаса, чтобы написать версию C. Ниже приведен код, если вам интересно:
#define CAPITAL 0
typedef struct city_distance {
size_t city;
uint32_t distance;
} city_distance;
int64_t minimumFuelCost(int32_t **roads, int32_t roads_size, int32_t *roads_col_size, int32_t seats){
size_t num_cities = roads_size + 1;
size_t *neighbors_counts = (size_t *)(calloc(num_cities, sizeof(size_t)));
for (size_t i = 0; i < roads_size; ++i) {
++neighbors_counts[roads[i][0]];
++neighbors_counts[roads[i][1]];
}
size_t **adj_list = (size_t**)(calloc(num_cities, sizeof(size_t*)));
for(size_t i = 0; i < num_cities; ++i) {
adj_list[i] = (size_t *)(calloc(neighbors_counts[i], sizeof(size_t)));
}
size_t* tops = (size_t *)(calloc(num_cities, sizeof(size_t)));
for(size_t i = 0; i < roads_size; ++i) {
size_t top_1 = tops[roads[i][0]];
size_t top_2 = tops[roads[i][1]];
adj_list[roads[i][0]][top_1] = roads[i][1];
adj_list[roads[i][1]][top_2] = roads[i][0];
++tops[roads[i][0]];
++tops[roads[i][1]];
}
free(tops);
uint32_t *distances = (uint32_t*)(calloc(num_cities, sizeof(uint32_t)));
bool *visited = (bool*)(calloc(num_cities, sizeof(bool)));
struct city_distance *frontier = (struct city_distance*)(calloc(num_cities, sizeof(struct city_distance)));
size_t top = 0;
frontier[0].city = CAPITAL;
frontier[0].distance = 0;
visited[0] = true;
for(size_t i = 0; i < num_cities; ++i) {
size_t city = frontier[top].city;
uint32_t distance = frontier[top].distance;
visited[city] = true;
distances[city] = distance;
--top;
for(size_t i = 0; i < neighbors_counts[city]; ++i) {
if(!visited[adj_list[city][i]]) {
++top;
frontier[top].city = adj_list[city][i];
frontier[top].distance = distance + 1;
}
}
}
free(frontier);
size_t *frontier_0 = (size_t*)(calloc(num_cities, sizeof(size_t)));
for(size_t i = 0; i < num_cities; ++i) {
frontier_0[i] = i;
}
int comp (const void *elem1, const void *elem2) {
size_t f = *((size_t *)elem1);
size_t s = *((size_t *)elem2);
if (distances[f] > distances[s]) return 1;
if (distances[f] < distances[s]) return -1;
return 0;
}
qsort(frontier_0, num_cities, sizeof(size_t), comp);
uint32_t *people_count = (uint32_t *)(malloc(sizeof(uint32_t)* num_cities));
for(size_t i = 0; i < num_cities; ++i) {
people_count[i] = 1;
}
top = num_cities;
while(top-->0) {
size_t city = frontier_0[top];
for(size_t i = 0; i < neighbors_counts[city]; ++i) {
size_t neighbor = adj_list[city][i];
if(distances[neighbor] < distances[city]) {
people_count[neighbor] += people_count[city];
}
}
}
free(distances);
free(frontier_0);
for(size_t i = 0; i < num_cities; ++i) {
people_count[i] = people_count[i] / seats + !!(people_count[i] % seats);
}
int64_t res = 0;
for(size_t i = 0; i < num_cities; ++i) {
res += people_count[i];
}
res -= people_count[CAPITAL];
free(people_count);
free(adj_list);
free(roads);
free(roads_col_size);
free(neighbors_counts);
return res;
}
Чтобы понять это чудовище, мне потребовалось меньше времени, чем, казалось бы, простую ошибку в одну строку в Python.
Причина в том, что код Python только выглядит простым, но на самом деле он очень сложен. Конечно, это легко, но все же не просто.
Воровство из статьи Лориса Кро Я хочу просто, а не просто легко
Простые системы можно разбить на более мелкие части, которые понятны по отдельности. Если вы внесете изменения в одну из этих частей, вам не придется опасаться неожиданных последствий в частях, не связанных напрямую с тем, над чем вы работаете. Сложные системы — полная противоположность: вам придется многое учитывать и действовать осторожно.
Пока,
Простые вещи обычно требуют меньше подготовки и могут быть выполнены даже неопытными людьми. По определению, сложные вещи требуют больше усилий, и не у всех всегда все получается.
Иллюзия того, что легко быть простым, не нова в программировании, на самом деле она существовала еще до того, как появился C, единственное, что, поскольку так мало людей знают разницу, ее очень трудно уловить.
Это то же самое, что заставило разработчиков FORTRAN задуматься: любая переменная, начинающаяся с i, j, k, l, m или n, должна быть целым числом, x, y и z должны быть комплексными, c и s должны быть 4. -байтовые символы, а все остальные должны быть действительными числами, если не указано иное.
Вы можете возразить, что это произошло из-за проблем с памятью, и в некоторой степени я с вами согласен, но вы не можете сказать мне, что они не предполагали, что это облегчит их работу или, по крайней мере, это не повлияет на них, потому что , `implicit none` была добавлена в язык намного позже, чем эта "функция", как и флаги компилятора.
Эта путаница понятий «легко» и «просто» также является причиной того, что продвижение типов как функция существует во многих языках; это также причина того, что у нас есть миллиард различных парадигм программирования, и все они делают программирование «проще», это также причина того, что Java «Write Once Run» Слоган Anywhere» привлекал людей, это также причина, по которой люди любят JS (и Python, если уж на то пошло), это также причина, по которой стандартная библиотека C++ представляет собой беспорядок, это также причина, по которой strtok, strtok_s и strtok_r существуют в C.
Единственная проблема заключается в том, что хотя простые вещи — это очень просто… они также во многих случаях сложны, или, проще говоря, то, как они работают, не очень интуитивно понятно. Например, возьмите любую из перечисленных выше вещей и попробуйте объяснить, как она работает. Как работает продвижение типов в статически типизированных языках? Как это работает в JS? Как это работает в Python? Как работает ООП? Как работает ФП? Как работает ПОП? Как JS и Python достигают своей простоты? Как они поддерживают типы внутри себя? Как работают их внутренние органы?
Когда вы сделаете это, вы поймете, что то, что вы считали простой задачей, на самом деле может стать лишь изогнутой линией в 100-мерном пространстве.
Итак, каково решение?
Мы уже обсуждали, насколько легко != просто и как часто обратное является истиной, но выявление проблемы — это лишь первый шаг в решении какой-то проблемы, поэтому давайте посмотрим на решение этой проблемы.
Наиболее реальным решением этой проблемы на данный момент является то, что разработчикам следует изучать свои языки, фреймворки и тому подобное на более низком уровне. Конечно, изучение ее до такой степени, чтобы вы могли воспроизвести компилятор, не является выполнимой задачей, но мы, как разработчики, должны, по крайней мере, знать достаточно, чтобы знать, что должна делать команда, например, как она хранится в оперативной памяти, т. е. в стек или куча, как он обрабатывается и т. д. без надлежащего знания этого очень сложно понять, когда что-то в вашей программе не так из-за особенностей языка.
Потому что, хотя новые языки, такие как Rust и Zig, наконец-то решают эту проблему, им все равно потребуется много времени, чтобы стать рыночным стандартом, и даже когда они это сделают, вам все равно придется этому научиться, потому что то, как эти языки решают эту проблему Проблема заключается именно в том, чтобы заставить разработчика изучить эти концепции.
Вам также следует стремиться писать простой код самостоятельно, поскольку эта проблема не ограничивается только разработкой языка. Ваш AbstractTokenBuilderFactoryInterface тоже является продуктом этой путаницы. Я знаю, что вы это сделали, я тоже, мы все когда-то это делали, но мы должны учиться на своих ошибках, а не повторять их.
Подтверждение
Если вы дошли до этой статьи, спасибо за прочтение, дайте мне знать, что вы почувствовали и какие области, по вашему мнению, мне следует улучшить. Я впервые пишу статью, поэтому я понимаю, что, должно быть, допустил некоторые очень очевидные ошибки, которых мне следует избегать, например, возможно, какая-то часть нуждалась в большей ясности, может быть, какая-то часть была слишком бессвязной, может быть, какая-то часть была ясна. но могло быть и лучше, возможно, какой-то контент был написан так, что это могло сбить с толку, или, может быть, проблема была в чем-то другом, я жду ваших критических и положительных отзывов.
