Поставить в начало последовательности нули, а затем единицы.

@ForQuestions · Регистрация: 10.10.2019

Студворк — интернет-сервис помощи студентам

Последовательность a1, a2, ... an, состоит из нулей и единиц. Поставить в начало этой последовательности нули, а затем единицы.

@Royal_X · 12.07.2024, 01:43

Сообщение от Алексей1153

посчитать сумму вектора - это быстрее

а почему ты думаешь, что там вектор? В условии ничего об этом не сказано. Ну а если каждый волен пофантазировать, то я говорю, что речь идет о битах и единички можно считать с помощью popcount (C++20) или майкрософтовских __popcnt16, __popcnt, __popcnt64 или __builtin_popcount, если GCC. Это будет быстрее, чем reduce для подсчета суммы вектора, ибо идет прямой вызов инструкции POPCNT.

@SaBuSEgine · 12.07.2024, 02:10

повар1, странный скрин у тебя, код скрыл и оставил только ошибку. Сам код поменял наверное

@Наталья8 · 12.07.2024, 02:48

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    char one[] = "1010001010111101010111000101010101111001";
    char two[125]{};
    short i{};
    while (*(one+i++) != '\0')
        if (one[i]==48)strncat(two, (const char*)(one+i), 1);
    while (i-->0)
        if (one[i]==49)strncat(two, (const char*)(one+i), 1);
    std::printf("%s\n", two);
    std::getchar();
    return 0;
}

Алексей1153 · 12.07.2024, 07:56

Сообщение от Royal_X

а почему ты думаешь, что там вектор

а кто мешает его сделать?
Даже если там файл, то можно читать в массив/вектор и так же суммировать.

Сообщение от Royal_X

__popcnt16, __popcnt, __popcnt64 или __builtin_popcount, если GCC.

ничего этого не нужно, достаточно указать в алгоритмах правильную политику распараллеливания

@повар1 · 12.07.2024, 10:50

Алексей1153, вместо вашего кода(вызвавшего дискусию) всего то надо записать одну строчку

C++
1
std::sort(vec.begin(),vec.end());

Снова считать не надо единички и нолики

Алексей1153 · 12.07.2024, 11:04

повар1, сортировка - это тоже долго и не линейно. По условию там одни нолики и единички

@повар1 · 12.07.2024, 11:12

Сообщение от Алексей1153

там одни нолики и единички

Нельзя отсортировать по вашему мнению?

@SmallEvil · 12.07.2024, 12:13

Сообщение от повар1

Нельзя отсортировать по вашему мнению?

Можно. Только неэффективно.
Можно применить сортировку подсчетом, что и делается.

Алексей1153 · 12.07.2024, 12:21

повар1, можно конечно. Ещё есть std::partition

@Royal_X · 12.07.2024, 13:31

Сообщение от Алексей1153

ничего этого не нужно, достаточно указать в алгоритмах правильную политику распараллеливания

все равно, твой метод медленнее, чем мой, какую бы политику ты бы не указывал. Кстати, конкретно в твоем случае, seq быстрее, чем par. Я протестировал на моем проце с 14 ядрами и 20 потоками.

std::popcount оказался быстрее более 20 раз твоего reduce с политикой seq, а вот про par даже не пишу, чтобы плакать не пришлось))

в тестах использовал твои числа

C++
1
std::vector<int> v{ 1,0,1,0,0,1,0,1,0 };

и

C++
1
auto x = std::bitset<9>("101001010").to_ulong();

вызывал миллион раз reduce для вектора и popcount для беззнакового длинного числа без оптимизации

Хорошая новость в том, что с оптимизацией, какой бы метод не выбрать, даже сортировку, код выполняется настолько быстро, что вся твоя болтовня о скорости нивелируется и не имеет смысла. Так что хватит тут чужие коды браковать и рассказывать, какие они медленные.

Алексей1153 · 12.07.2024, 13:55

Сообщение от Royal_X

seq быстрее

само собой, что векторизация для данной задачи быстрее, чем создание потоков

Сообщение от Royal_X

в тестах использовал твои числа

это не мои числа. Мои числа тут были бы мегабайта на 4

Добавлено через 37 секунд

Сообщение от Royal_X

с оптимизацией

само собой, что с ней нужно измерять

@Royal_X · 12.07.2024, 14:02

Сообщение от Алексей1153

само собой, что с ней нужно измерять

с оптимизацией умный компилятор настолько меняет всё (даже саму первоначальную идею погромиста), что

Сообщение от Royal_X

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

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

Алексей1153 · 12.07.2024, 14:05

Сообщение от Royal_X

акой бы метод не выбрать, даже сортировку, код выполняется настолько быстро

а ты уже опробовал это на мегабайтных векторах?

@Royal_X · 12.07.2024, 14:19

Сообщение от Алексей1153

а ты уже опробовал это на мегабайтных векторах?

у ТС не написано о количестве элементов в последовательности, следовательно, каждый волен брать сколько угодно чисел. Ты взял 9 элементов и показал некий волшебный код, подав это в таком соусе, мол коды остальных говно, а твой прям идеальный. Я же написал, что для этих конкретных 9 элементов можно и быстрее, так что лучше молчать о скорости.
И почему не опробовать сразу на гигабайтных векторах))

Добавлено через 6 минут
Алексей1153, кстати, есть и vec_popcnt, если что, + различные библиотеки, которые задействуют инструкцию popcnt для вектора битов

кстати, посмотрел, оказывается мой проц поддерживает avx2 и bmi2, так что можно что-то покруче даже сделать, чем решение на popcnt

Алексей1153 · 12.07.2024, 14:31

Сообщение от Royal_X

подав это в таком соусе, мол коды остальных говно

это твои фантазии, я такого не писал

@Наталья8 · 12.07.2024, 15:44

Сообщение от Royal_X

твой метод медленнее, чем мой

А я не думаю, что мой код (который выше) сильно медленнее.
Я просто написал, и ни чего не думаю.

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

Добавлено через 53 минуты

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
    std::string jne{"1000011101010001111010"};//
    short count = jne.length(), cnt{};
while (count--) {
        if (jne[0] == 48)jne += "0";
        else ++cnt;
        jne.erase(0, 1);
    }
while (cnt--)jne += "1";
 
std::printf("%s\n", jne.c_str());
    return 0;
}

@SmallEvil · 12.07.2024, 18:29

Сообщение от Наталья8

Написать на каких то костылях, и вести дискуссии, у кого они быстрее?

Про быстрее: тут прицепились к небольшому замечанию.
Тут дело не в быстроте, а в "чистоте" кода.

Добавлено через 1 минуту
Да пусть себе будут все варианты, но только рабочие.

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

@ForQuestions 0 / 0 / 0 Регистрация: 10.10.2019 Сообщений: 12

	Поставить в начало последовательности нули, а затем единицы. 13.10.2019, 18:36. Показов 7141. Ответов 36 Метки нет (Все метки) Последовательность a1, a2, ... an, состоит из нулей и единиц. Поставить в начало этой последовательности нули, а затем единицы. 0

@SaBuSEgine 1 / 1 / 0 Регистрация: 02.07.2024 Сообщений: 14
	12.07.2024, 02:10
	повар1, странный скрин у тебя, код скрыл и оставил только ошибку. Сам код поменял наверное Миниатюры 0

Алексей1153 фрилансер 6499 / 5730 / 1133 Регистрация: 11.10.2019 Сообщений: 15,321
	12.07.2024, 11:04
	повар1, сортировка - это тоже долго и не линейно. По условию там одни нолики и единички 0

Алексей1153 фрилансер 6499 / 5730 / 1133 Регистрация: 11.10.2019 Сообщений: 15,321
	12.07.2024, 12:21
	повар1, можно конечно. Ещё есть `std::partition` 0