Задачка по SQL
Есть таблица Т с одним численным полем F. Нужно написать запрос на ANSI SQL, который бы возвращал n — ое максимальное значение.
Например имеем значения в таблице: 1, 2, 3, 4, 5, и n = 2. Результат — 4.
Есть идеи как решить?
crypto5, SWE
Facebook
Twitter
LinkedIn
crypto5
Все операции которые ты указал не являются атомарными в Java и могут стать жертвами race condition. В джава есть набор классов Atomic*, которые реализуют логику атомарности для разных операций (числовая арифметика, работа с сылками обьектов), а также ключевое слово volatile.
Каждая из таких атомарных операций видимо по своему и по разному транслируется в ассемблер в зависимости от JVM, и аппаратной платформы. Иногда выгоднее сделать короткий лок, иногда заимплементить lock-free алгоритм, для реализации которых видимо тоже существуют разные подходы. Думаю что однозначного короткого ответа на твой вопрос нету.
Каждая из таких атомарных операций видимо по своему и по разному транслируется в ассемблер в зависимости от JVM, и аппаратной платформы. Иногда выгоднее сделать короткий лок, иногда заимплементить lock-free алгоритм, для реализации которых видимо тоже существуют разные подходы. Думаю что однозначного короткого ответа на твой вопрос нету.
Ну, а если тебе нужно найти lock-free алгоритм для конкретной операции и архитектуры, наверное можно что-то нагуглить.
anonymous
Возьм Java, чесно скажу что исходников реализации работы с указателями я не видел (но я видел как это сделанов Сях), но готов предположить что присвоение указателя превращаеться с более чем одну процессорнцю операцию (как минимум присвоение и подсчет ссылок), краш может быть из-за того что выполнив часть операции (присвоения указателя) управление может пересться блоку кода который его читает или меняет (читай присвает) и он перетрет часть данных которые были выполнены первым присвоением, и когда управление вернеться к первому присваивателю то к чему это приведет:) сложно предсказать
идея очень проста — свести все к операции которая изменит состоянии системы за 1 такт процессора, а таких много:) например инкрементация инта (хотя для Java я бы сперва проверил, но сложно предположить какие дополнительные инструкции можно придумать для такой простой команды:))
Если использовать умный указатель с подсчетом ссылок, то я не вижу где там может случится краш.
ПыСы — это очень простая задача, просто я мало видел нормальной реализации, может хоть тут мы ее запечатлеем:)
Думаю что задача непростая, и имеет множество стратегий решения, каждая из которых является компромисом с каким нибудь фактором (производительность, целостность). Тот же optimistic locking имеет вполне осязаемые недостатки.
если речь идет об умных указателях, то там операция выполняеться не за 1 такт процессора и это тоже может повлечь краш
подмена указателя это хорошо, но что тогда делать со старым?
хранить? — будет «течь» память
грохнуть — можно поломать логику, так как может быть код который его использует
хранить? — будет «течь» память
грохнуть — можно поломать логику, так как может быть код который его использует
ПыСы — это очень простая задача, просто я мало видел нормальной реализации, может хоть тут мы ее запечатлеем:)
Можно перенести, можно поменять ссылку с старого обьекта на новый (скрытый).
ок, возьмем optimistic locking, как вы бы реализовали его камит:) ведь нужно перенести данные из обьекта сткрытого от пользователя к тому который активно им используеться?
Наверное обьекты синхронизации не обязательно выносить в kernel space, они могут (если мы говорим о user space приложении, а не куске ядра) прекрасно себя чувствовать в user space.
Во вторых очевидно что лок локу рознь. То есть нужно вводить разные локи — на чтение, на запись и т.д. и таким образом снижать количество ждущих операций.
Ну и в третьих — если мало конкурентных пересекающихся на записи транзакций — то можно использовать optimistic locking, в котором собственно никаких локов нету.
Во вторых очевидно что лок локу рознь. То есть нужно вводить разные локи — на чтение, на запись и т.д. и таким образом снижать количество ждущих операций.
Ну и в третьих — если мало конкурентных пересекающихся на записи транзакций — то можно использовать optimistic locking, в котором собственно никаких локов нету.
Вообще вопрос конечно поставлен очень обще.
проблема в том что есть некий обьект, к которому одновременно обращаються потому на чтение и запись, проблема в том как с минимумом усилий для операционной системы (каждый лок, переключение контекста в режим ядра, ожидание это удар по производительности) сделать так что бы система работала:)
примером может выступить любой сервер, в нем есть кучу структур которые отражают состояние, и часть пользователей его модифицируют, часть читают.
А можешь в двух словах описать свое видение этой проблемы, потому что почитав википедию, я так и не понял на какой вопрос нужно отвечать?
Ok:) в ответ могу предложить задачку с промышленым смыслом: попробывать решить Readers-writers problem без обьектов синхронизации, я думаю какой в этом промышленый смысл в высоко нагруженых системах и так ясно:) решение я знаю, может быть у вас есть свое и оно интереснее
Зачем это, я не знаю. Упражнение. Просто придумалось ужесточить условие после того, как прочитал исходный вопрос.
Я бы на собеседованиях не давал, но встречал подобное.
Я встретил эту задачку на одном форуме, и честно говоря не додумался до твоего решения, но мне было интересно как она решается.
у меня только один вопрос:) зачем это? для собеседований на логику слабовато, так как задача контектно-зависимая (знания SQL) для проверок знаний СУБД тож глухо, больше нужны люди которые план умеют читать, индексы правильно строить и нормализацию делать итд...
тогда ловите таконе решение
SELECT
t.n
FROM
table t
WHERE
(SELECT COUNT (1) FROM table t_s WHERE t_s.n > t.n) = pos — 1
SELECT
t.n
FROM
table t
WHERE
(SELECT COUNT (1) FROM table t_s WHERE t_s.n > t.n) = pos — 1
конечно можно рассмотреть случаи когда цифры повторяються, но идея таже
С синтаксисом SQL знаком плохо.
SELECT < n-ю строку> F FROM (SELECT DISTINCT F FROM T ORDER BY F DESC)
вся соль в том, как сделать SELECT < n-ю строку> с указанными ограничениями:)
у меня наводящие вопросы:1. один
1. это должен быть один запрос или можно скоп
2. можно ли использовать переменые
3. можно ли использовать временые таблицы, вьюхи итд...
4. что есть приоритет в этой задаче? (скорость, размер кода, оригинальность...)
2. есть переменная N из условия задачи, больше ничего
3. нет
4. без приоритетов. просто решение, удовлетворяющее условиям.
С синтаксисом SQL знаком плохо.
SELECT < n-ю строку> F FROM (SELECT DISTINCT F FROM T ORDER BY F DESC)
я лет 5−6 занимался подобной проблемы и в те времена MS SQL и ANSI SQL не всегда сходились, поэтому я бы предпочел на клинствои уровне породить 2 наследника, а нужные методы бизнес логики перегружать правильными запросами, поэтому и спросил...
насчет автогенерить SQL — не получиться так как есть ограничение на строку запроса
у меня наводящие вопросы:
1. это должен быть один запрос или можно скоп
2. можно ли использовать переменые
3. можно ли использовать временые таблицы, вьюхи итд...
насчет автогенерить SQL — не получиться так как есть ограничение на строку запроса
у меня наводящие вопросы:
1. это должен быть один запрос или можно скоп
2. можно ли использовать переменые
3. можно ли использовать временые таблицы, вьюхи итд...
4. что есть приоритет в этой задаче? (скорость, размер кода, оригинальность...)
junior_dev
Изначально задача была написать портабельной между ораклом и мс сервером решение. Но я решил обобщить ее до ANSI SQL (как видно из первого поста).
Sergey Khenkin
Я думал над этим, и нашел два решения:
1. Делать временную таблицу с аутоинкрементным полем.
2. Динамически генерировать запрос для каждого N, например если N=2, то запрос будет таким:
select max (f) from T where f not in (select max (f) from T)
Изначально задача была написать портабельной между ораклом и мс сервером решение. Но я решил обобщить ее до ANSI SQL (как видно из первого поста).
Sergey Khenkin
Я думал над этим, и нашел два решения:
1. Делать временную таблицу с аутоинкрементным полем.
2. Динамически генерировать запрос для каждого N, например если N=2, то запрос будет таким:
select max (f) from T where f not in (select max (f) from T)
А твое какое решение?
OK. А теперь сделаем задачку интересней. Условие то же, но пользоваться вещами типа: OFFSET, FETCH FIRST, ROW_NUMBER (), OVER, LIMIT, TOP, SKIP, FIRST и т.д. — то есть всем тем, что описано по ссылке gonzo нельзя.:)
Например для оракла лучше через RowNum, а MS 2005+ поддерживает ROW_NUMBER ()
а какая СУБД? ато что-то варианты для Oracle и MS SQL там выглядят староватенько
26 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів