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

@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 минуту
Да пусть себе будут все варианты, но только рабочие.

Новые блоги и статьи Все статьи Все блоги /
тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .

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

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

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

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

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