Java, C++ qsort, countsort Можно ли сделать код еще быстрее?

ВНИМАНИЕ: Java код ниже чем С++ код!

// Swap two elements - Utility function  
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 
   
// partition the array using last element as pivot
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];    // pivot 
    int i = (low - 1);   
   
    for (int j = low; j <= high- 1; j++) 
    { 
        //if current element is smaller than pivot, increment the low element
        //swap elements at i and j
        if (arr[j] <= pivot) 
        { 
            i++;    // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
   
//quicksort algorithm
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        //partition the array 
        int pivot = partition(arr, low, high); 
   
        //sort the sub arrays independently 
        quickSort(arr, low, pivot - 1); 
        quickSort(arr, pivot + 1, high); 
    } 
}
int main() 
{ 
    int arr[] = {12,23,3,43,51,35,19,45}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout<<"Input array"<<endl;
    displayArray(arr,n);
    cout<<endl;
    quickSort(arr, 0, n-1); 
    cout<<"Array sorted with quick sort"<<endl; 
    displayArray(arr,n); 
    return 0; 
}

Java. Сортировка подсчетом. Как повысить быстродействие?

Code review.

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

Программа сортирует 1 млн. целых чисел двумя разными способами. Хотелось бы сделать побыстрее.

import java.util.ArrayList;


import java.util.Collections;
import java.util.Hashtable;
import java.util.Random;

public class Test {


    
    private static final int MAX_SORT_SIZE = 10000000;

    private static ArrayList<Integer> mysort(ArrayList<Integer> list) {


        Hashtable<Integer, Integer> ht = new Hashtable<Integer, Integer>();
        for(int i=0;i<MAX_SORT_SIZE;i++) {
            int num = list.get(i);
            
                Integer value = ht.get(num);
                if(value==null) ht.put(num,num);
                else { 
                    ht.remove(num);
                    
                    ht.put(num,value+num);
                }
        }
        
        int n=0;
        ArrayList<Integer> res= new ArrayList<Integer>();
        for(int i=0;i<MAX_SORT_SIZE;i++) {
            Object obj =  ht.get(i) ;
            if(obj==null) continue;
            Integer value = new Integer((Integer)obj);
            
            if(value==i)  {    res.add(value);           }
            else {

                    ht.remove(i);


                    ht.put(i,value-i);
                    res.add(i);
                    i--;
            }
            
        }
        
        
        return res;
    }

    public static int getRandomInt(int from, int excluded_border) {


        return new Random().nextInt(excluded_border)+from;
    }
    
    public static void main(String[] args) throws Exception {
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        for(int i=0;i<MAX_SORT_SIZE;i++) {
            int n = getRandomInt(0,MAX_SORT_SIZE);
            list.add(n);
            list2.add(n);
        }
        
        long before = System.currentTimeMillis();
        Collections.sort(list);
        long after = System.currentTimeMillis();
        System.out.println("Time: "+(after-before));
        
        for(int i=0;i<20;i++) {
                System.out.println(list.get(i));
        }
        
        System.out.println("\n================================");
        
        long before2 = System.currentTimeMillis();
        list =  mysort(list2);
        long after2 = System.currentTimeMillis();
        System.out.println("Time mysort: "+(after2-before2));
        
        for(int i=0;i<20;i++) {
            System.out.println(list.get(i));
        }    
        System.out.println("\n================================");
     
    }    
}
👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Сделал быстрее. Вот два кода. Один java, другой c++


//C++
size_t * mysort3d(size_t arr[],  size_t sz ) {
 
	cout  << endl << "============ MY SORT 3D PACK ===========" << endl;

	if(sz<100)   {
		for (size_t i=0; i < sz; i++)  cout<<arr[i]<<" ";   
	} 

	cout << endl;
		
	struct timeval tp;
	gettimeofday(&tp, NULL);
	long long ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;

	//cout << "Milliseconds from: " << ms << endl;
		
	////////////////////////////////////////////////////////
	 
	size_t * arr2 = new size_t[sz];
	for (size_t j = 0; j < sz; j++) arr2[j]=0;
		  
	  
	for (size_t j = 0; j < sz; j++) {
		arr2[arr[j]] ++;
	}
		
	  
	gettimeofday(&tp, NULL);
	long long ms2 = tp.tv_sec * 1000 + tp.tv_usec / 1000;
	cout << "Milliseconds passed: " << (ms2-ms)  << endl;
	cout << "Array sorted with MY SORT 3D " << endl; 
	CheckSorting(arr2,sz);
	  
	if(sz<100)  {
		for (size_t i=0; i < sz; i++)  cout<<arr2[i]<<" ";  
	}
	cout << endl;
	  

	return arr2;
   
}

void depackRes( size_t arr[],  size_t sz ) {
    
    struct timeval tp;
    gettimeofday(&tp, NULL);
    long long ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;

	cout << "Milliseconds from: " << ms << endl;

    size_t * res2 = new size_t[sz];
    
	size_t k=0;
    for(size_t n=0;n<sz;n++) {
      for(size_t m=0;m<arr[n];m++)
      res2[k++]=n;
    }


    gettimeofday(&tp, NULL);
    long long ms2 = tp.tv_sec * 1000 + tp.tv_usec / 1000;
    cout << "Milliseconds passed: " << (ms2-ms)  << endl;
    cout<<"Array depacked with MY SORT 3D   "<<endl; 
    CheckSorting(res2,sz);

	if(sz<100)  {
       for (size_t i=0; i < sz; i++)  cout<<res2[i]<<" ";  
	}

	cout << endl;
    
}

//main... depackRes(mysort3d(arr2,sz),sz);

///И Java далее


    private static int[] unpackRes(int[] res) {
	
		int[] res2 = new int[res.length];
		int k=0;
		for(int n=0;n<res.length;n++) {
			for(int m=0;m<res[n];m++)
			res2[k++]=n;
		}
		return res2;
		
	}

	private static int[] sort3darr(int[] ish) {

		int sz = ish.length;
		int[] res = new int[sz];
		int m=0;
		
		for(int n=0;n<sz;n++) res[ish[n]]++;
		    
		return res;
		
	}

    private static void test1(int[] res) {
	
		System.out.println("\n============== Sort test ==================");
		String s="Test ok. All sorted";
		for(int u=1;u<res.length;u++) {
				if(res[u]<res[u-1]) {
					s = "Test NOT ok. Unsorted";
				}
		}
		System.out.println("\n============= Result of test: "+s+" ===================");
	}

    public static void main(String[] args) throws Exception {

		int[] ish = new int[MAX_SORT_SIZE];
		for(int i=0;i<MAX_SORT_SIZE;i++)  ish[i]=n;
			
		System.out.println("\n============== 3d sort==================");

		long before7 = System.currentTimeMillis();
		int[] res = unpackRes(sort3darr(ish));
		long after7 = System.currentTimeMillis();

		System.out.println("\n3d Diff: "+(after7-before7));
				
		for(int i=0;i<20;i++) {
			System.out.print(unpack(res, i)+", ");
		}

		test1(res);

    }

Java. Сортировка подсчетом. Как повысить быстродействие?

Code review.

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

Программа сортирует 1 млн. целых чисел двумя разными способами. Хотелось бы сделать побыстрее.

import java.util.ArrayList;


import java.util.Collections;
import java.util.Hashtable;
import java.util.Random;

public class Test {


    
    private static final int MAX_SORT_SIZE = 10000000;

    private static ArrayList<Integer> mysort(ArrayList<Integer> list) {


        Hashtable<Integer, Integer> ht = new Hashtable<Integer, Integer>();
        for(int i=0;i<MAX_SORT_SIZE;i++) {
            int num = list.get(i);
            
                Integer value = ht.get(num);
                if(value==null) ht.put(num,num);
                else { 
                    ht.remove(num);
                    
                    ht.put(num,value+num);
                }
        }
        
        int n=0;
        ArrayList<Integer> res= new ArrayList<Integer>();
        for(int i=0;i<MAX_SORT_SIZE;i++) {
            Object obj =  ht.get(i) ;
            if(obj==null) continue;
            Integer value = new Integer((Integer)obj);
            
            if(value==i)  {    res.add(value);           }
            else {

                    ht.remove(i);


                    ht.put(i,value-i);
                    res.add(i);
                    i--;
            }
            
        }
        
        
        return res;
    }

    public static int getRandomInt(int from, int excluded_border) {


        return new Random().nextInt(excluded_border)+from;
    }
    
    public static void main(String[] args) throws Exception {
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        for(int i=0;i<MAX_SORT_SIZE;i++) {
            int n = getRandomInt(0,MAX_SORT_SIZE);
            list.add(n);
            list2.add(n);
        }
        
        long before = System.currentTimeMillis();
        Collections.sort(list);
        long after = System.currentTimeMillis();
        System.out.println("Time: "+(after-before));
        
        for(int i=0;i<20;i++) {
                System.out.println(list.get(i));
        }
        
        System.out.println("\n================================");
        
        long before2 = System.currentTimeMillis();
        list =  mysort(list2);
        long after2 = System.currentTimeMillis();
        System.out.println("Time mysort: "+(after2-before2));
        
        for(int i=0;i<20;i++) {
            System.out.println(list.get(i));
        }    
        System.out.println("\n================================");
     
    }    
}

Уберите нафиг хештейбл, работайте просто с массивом где индекс это само число.

Как быть с выходом за пределы массива? У ht такой проблемы нет.

Массив размером в 4 гигабайта вам в помощь :) и получите максимально достижимую скорость О(n) :)

Давайте код, закину в эклипс, посмотрим.

Как повысить быстродействие?

Не писати на Java.

чому своп зроблено в С стилі, а не через std::swap?
пля, та там все Сний код, перепиши на С++ і взлетить :)

і перейменуй заголовок, зря зайшов, думав занятний срач буде :(

Сейчас смотрю, ту же функцию

swap

можно и инлайном сделать.
Хотя не факт, что компиллер, при оптимизации, и так его инлайном не сделает.

Слово inline немного влияет на приоритет инлайнинга, но я очень удивлюсь, если без него компилятор не додумается заинлайнить. По крайней мере когда мы говорим про свап двух интов.

Да и во всех мейнстримных реализациях стандартной библиотеки std::swap отмечен inline (constexpr с 20 стандарта, что также подразумевает inline для функций).

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

Ну так , навскидку, то алгоритм сортировки можно распараллелить — будет намного быстрее.
Если говорить, то сингл-срединг, то нужно в код вникать.

Да, quicksort определенно можно сделать многопоточным.

алгоритм сортировки можно распараллелить — будет намного быстрее

Не буде швидше

Согласно последних комментариев всех заинтересованных лиц, мой алгоритм работает иногда быстрее O(n) и является смелой интерпретацией сортировки подсчетом.
У него есть определенные устранимые недостатки, что многообещающе.
Осталось допилить некоторые моменты и оформить как библиотеку, после чего включать в другие свои проекты.
Всем спасибо за проявленное внимание!

Я правильно понимаю, что для сортировки 50 млн элементов понадобится пару гиг стека, чтобы обслуживать рекурсивные вызовы функции с параметрами?

Так мой алгоритм это что-то вроде сортировки подсчетом. Там нет рекурсии. Только циклы.
Посмотри в конце видео исходный код функции mysort
Что касается жора (повышенного потребления/повышенной нужды в) памяти — ага. Я обдумываю сейчас как бы это исправить.
Это std::qsort рекурсивный, но я его взял для сравнения только.

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

:))) Зато просмотры идут. Ладно, я вот разберусь как устроен гитхаб и размещу там новую версию.

иногда быстрее O(n)

Это даже в теории невозможно.
Это означает, что некоторые элементы ты ниразу не посетил. Если не посетил, то откуда ты знаешь на правильном ли они месте в сортировке ?

Я посещаю все. Во втором массиве они становятся индексами. Скоро выложу исходники на гитхабе.

Я посещаю все.

Це як мінімум O(n).

Во втором массиве они становятся индексами

По пам’яті у тебе теж O(n)?

Схоже, що ти «винайшов» ось це — uk.wikipedia.org/...​ki/Сортування_підрахунком. Проблема з цим алгоритмом — використання додаткової пам’яті та робота лише з числами.

Это даже в теории невозможно.

Може якісь обгортки навколо зростаючих послідовностей так що не треба дивитися в елемент щоб знати його значення... Але це означає, що простих масивів буде недостатньо і потрібна підготовка таких метаданих.

Вот о чем-то таком я тоже думал. Следует ли подготовку учитывать как время работы самого алгоритма? Можно ведь выдавать полуфабрикат и юзать его (готовить на месте) ...

мой алгоритм работает иногда быстрее O(n)

фейспалм. идите учите теорию, потому что вы видимо вообще не понимаете что происходит

Заинтриговал :)
Джаст фо фан, отсортируй своим алгоритмом массив из двух чисел  {0, std::numeric_limits<size_t>::max() }

Посмотри на introsort, он же Introspection Sort.
Именно он используется в std::,
по крайней мере в gcc.
А у quicksort в худшем случае квадратичная временная сложность...

Кроме всего прочего, обмен можно сделать без временной переменной:
x = x ^ y;
y = x ^ y;
x = x ^ y;
Но спрашивается, зачем эти велосипеды, если есть std::swap?

Хотя, с временной переменной, возможно, будет быстрее, за счёт меньшего (на одну) числа операций.
Но не уверен, нужно проверять (что быстрее, xor или выделение/удаление на стеке).

Это будет работать медленнее или вообще не будет работать, если x и y заалиасены (ссылаются на один и тот же адрес)

Универсальный (да как сказать, даже специализированный — навряд ли) не может работать быстрее O(n).

Я не уявляю як на серйозних щах можна нести таку нісенітницю

иногда быстрее O(n)

Вы совершенно не понимаете смысла О-большое.

Я там просто забыл смайлик поставить. О(н+к) — of course, sure
Тема про сортировки и их реализации получилась.

Вот в этой книге: «Роберт Седжвик: Фундаментальные алгоритмы C++. Части 1-4»
Прямо в первой главе, там где код алгоритма поиска связи, как раз намек на мою реализацию сортировки.
P.S.
Ну или можете посмотреть вот это мое видео:
youtu.be/8qer-tUa_-E
С днем системного администратора всех!!!

P.S. Смотреть видео надо на широком экране, чтобы было более-менее четко видно.

Оптимізацію використовували при компіляції?
wiki.gentoo.org/wiki/GCC_optimization/ru

Спробуйте -O3

К чему вообще приведет такое вот улучшение (в виде убыстрения) существующих методов сортировки? В мировом масштабе?

Олег, скажу честно, я 10 лет назад зафигачил его на CUDA и все эти мелки однопоточные оптимизации,,, вообщем можно про них вообще зыбыть.

Только об этом никто не знает?

Что все равно std::sort или сишный квиксорт народ использует.

Если есть граничные условия, то сортировку можно провести вообще со сложностью O(N), ищите Bucket sort. Правильно применять алгоритмы часто круче оптимизации кода.
ru.wikipedia.org/wiki/Блочная_сортировка

Сам такую использую в компьютерном зрении.

Пока вот так и отлично осиливает 50 млн записей.
За 19152 милисекунд. А моя сортировка делает тоже самое за 2642 милисекунд.
Пошел я спать. Наверное я где-то ошибся в коде.


int main(int argc, char *argv[]) 
{ 

    char *p;
    if (argc <= 1)
	{
		if (argv[0])
			std::cout << "Usage: " << argv[0] << " <number>" << '\n';
		else
			std::cout << "Usage: <program name> <number>" << '\n';
 
		exit(1);
	}
 
	size_t sz = strtol(argv[1], &p, 10);
	
    cout << "Hello World  Size of array = " << sz << endl;
  
 size_t * arr = new size_t[sz];
   size_t * arr0 = new size_t[sz];
   size_t i=0;
   
   for(i=0;i<sz;i++){
   size_t d = rand()%sz;
     arr[i]= d;
     arr0[i] = d;
   }

    cout<<"Input array"<< endl;

  if(sz<100)  {
     for (i=0; i < sz; i++)  cout<<arr[i]<<" ";   
  }
    cout<<endl;

    struct timeval tp;
    gettimeofday(&tp, NULL);
    long long ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;

    //std::sort(arr,arr+sz);
    
    std::qsort(
        arr,
        sz,
        sizeof(size_t),
        [](const void* x, const void* y) {
            const int arg1 = *static_cast<const int*>(x);
            const int arg2 = *static_cast<const int*>(y);
            const auto cmp = arg1 - arg2;
            if (cmp < 0) return -1;
            if (cmp > 0) return 1;
            return 0;
        });
  
  //quickSort(arr, 0, sz-1); 

    gettimeofday(&tp, NULL);
    long long ms2 = tp.tv_sec * 1000 + tp.tv_usec / 1000;

    cout << "Milliseconds from: " << ms << endl;
    cout << "Milliseconds passed: " << (ms2-ms)  << endl;
    cout<<"Array sorted with quick sort"<<endl; 

  if(sz<100)  {

      for (i=0; i < sz; i++)  cout<<arr[i]<<" ";   

  }

  //  mySort(arr0,sz);

    delete arr;
    delete arr0;
    return 0; 
}
if (argc <= 1)
{
if (argv[0])

Здесь нет ошибки ?

К несчастью, не падало, когда запускал вот так: helloworld 500000 (argc был равен 1)
Угловую скобочку надо повернуть. Копипаста-такая-копипаста.

Нет тут ошибки, читай стандарты. В новых стандартах и POSIX и C и C++ argc может быть равен нулю в случае использования специального запуска программы с полностью пустыми параметрами, но стандарт требует чтобы argv[argc] был равен NULL всегда. Т.е. если даже argc = 0, то argv[0] = NULL. Другое дело что эти танцы вокруг argv[0] не нужны в вышеприведенном примере, опять же если этот helloworld не будет использоваться в качестве login shell и т.п. вещей.

быстрее... поддерживаемый? или исполняемый? если исполняемый, то зачем, какую проблему решаем? Если просто курс алгоритмов проходим (+ там есть проверка каким-то ботом... привет девклаб =)), то это да, имеет смысл, но не пишите потом такое коллегам в проде =)

Ну это реализация из интернета нагуглена. Я ее скопипастил в vscode а она почти не работает. Возможно мне когда-то понадобится сортировать очень много чисел и очень быстро.

Какой-то очень «сишный» C++.
Про алгоритмы уже достаточно отвечали в этой теме, так что немного покритикую сам код, может это тоже будет полезно.

В плюсах стоит использовать std::swap вместо ручного велосипеда. Если только у тебя нет цели попрактиковаться в написании таких велосипедов.
Если же цель была такая — почитай про ссылки и чем они отличаются от указателей. Swap должен принимать именно ссылки: так и не придётся задумываться, не подсунут ли в функцию nullptr (ссылка не может быть нулевой), и не придётся постоянно брать адрес, чтобы потом разыменовывать.

Пре-инкремент лучше пост-инкремента во всех случаях, где пост-инкремент не является явной необходимостью.
Да, для интов это роли не играет, любой оптимизатор всё лишнее без труда выкинет. Но когда потом будешь работать с итераторами, это может оказаться довольно важным (пост-инкремент может делать больше работы, в данном случае совершенно лишней) — так что лучше привыкать сразу юзать ++i by default.

Если у тебя относительно свежий компилятор, на котором доступен стандарт C++17, то размер массива стоит определять с помощью std::size, а не этой громоздкой конструкцией sizeof(arr)/sizeof(arr[0]). Она мало того что некрасива, так ещё и несколько опасна: код потом может быть отрефакторен, массив заменён на что-то другое (например, на голый указатель) — а эта строчка так и продолжит компилиться, выдавая абсолютно неправильный результат.
std::size же сразу ругнётся в таком случае.

Для размеров и индексов стоит использовать беззнаковый тип.
В стандарте это std::size_t.
Хотя в некоторых случаях может иметь смысл и юзать unsigned int, который на многих платформах меньше по размеру и процессор с ним может шустрее работать (если, конечно, количество элементов в массиве не исчисляется миллиардами).

std::endl использовать стоит чуть чаще чем никогда, поскольку endl = ’\n’ + flush. А flush в явном виде вызывать нужно крайне редко.
При работе с консолькой это может быть и не сильно заметно, но вот когда придёт время работать с файлами (если для этого будут использоваться стандартные стримы) — вызовы flush, которые неявно дёргаются из endl, могут очень сильно ударить по производительности, сношая жёсткий диск/ссд при записи каждой строчки.

Спасибо, все учту. Сначала добьюсь 50 млн чисел. Чтобы не падало, а сортировало.

Для размеров и индексов стоит использовать беззнаковый тип.
В стандарте это std::size_t.

Почему? ssize_t очень удобен, когда функция возращает [-1, SSIZE_MAX]. Например −1 — объект не создан и не имеет размера, в то время как 0 — вполне легальный размер для, например, new int[0].

Потому что стандартная библиотека везде принимает и возвращает size_t по умолчанию, будет меньше проблем при взаимодействии с ней.
Ну и на некоторых архитектурах с беззнаковыми числами процессор может работать чуть быстрее (хотя да, у знаковых в плане перформанса может быть преимущество, связанное с тем, что их переполнение undefined и, соответственно, можно выбросить какие-то проверки связанные с этим).
Так что если говорить чисто про перформанс, когда нужно выжать из процессора максимум, — не всё так однозначно и надо профайлить.

Для описанных тобой сценариев — согласен, использовать знаковый тип удобно. Но у автора не тот случай. Да и я на практике с такими сталкиваюсь довольно редко.
Чаще вижу, что в качестве специального невалидного значения возвращают то же самое −1, но кастнутое к возвращаемому беззнаковому типу (валидным индексом ведь оно уже быть не может, т.к. это максимальный возможный размер). Так, например, работает std::string::find.

Чаще вижу, что в качестве специального невалидного значения возвращают то же самое —1, но кастнутое к возвращаемому беззнаковому типу

Это источник больших проблем. В С++ нельзя автоматизировать каст, например, преврати беззнаковый тип в знаковый, значит программеры хардкодят тип и если был int для возврата −1, а потом тип стал 64 бит, то получим 0×00000000FFFFFFFF, что не будет −1.

Согласен, что это может приводить к проблемам. Особенно, например, при переводе 32-битных продуктов на 64-битную архитектуру, если в каком-то коде юзали типы unsigned int или unsigned long вместо православного size_t.

Но с формулировкой «источник больших проблем» не соглашусь.
Во-первых, если использовать size_t везде, проблемы не будет. По крайней мере при переходе на 64-битную архитектуру с 32.
Во-вторых, если по какой-то причине нужно не size_t, а что-то другое, — захардкоженное значение static_cast<???>(-1) можно инкапсулировать в глобальную константу и использовать её для сравнения, чтоб не писать касты каждый раз.
В-третьих, юнит-тесты должны детектить подобные проблемы без особого напряга. Если их в принципе пишут.

Эксепшены — это EXCEPTIONS, а не коды возврата.

Конечно нет, эксепшены лучше кодов возврата

Наоборот, перфоманц будет только более быстрее

Бенчмарк в студию, напр. на 1м экспешнинов и 1м рет вельюс. Можешь взять любой понравившийся язык, я не возражаю.

Зачем бросать миллион эксепшенов? Это даже в жабе моветон

конечно, и именно поэтому в С++ добавили noexcept: чтобы функция сильно быстро не работала

noexept потрібен в тому числі щоб компілятор міг вибрати між move та copy конструктором.

Ну, це коли мова йде про використання об’єктів зі стандартними контейнерами. Не з усіма об’єктами їх використовують.

Але так, хороше правило by default: позначати move constructor і move assignment operator як noexcept, коли це можливо.

Щодо інших функцій — питання неоднозначне.
З одного боку, це непогано документує код для інших девелоперів, а також дозволяє темплейтному коду приймати рішення на підставі того, чи гарантує певний виклик 100% відсутність ексепшенів (подібно тому, як це робить std::vector при релокації своїх елементів).
З іншого — сама функція може стати повільнішою через вимогу стандарту детектити порушення «контракту» і викликати terminate.

Если эксепшн бросается прям реально редко, когда прям реально что-то пошло очень сильно не так, — его использование может и не помешать перформансу. А может даже помочь, ибо из «hot path» уберётся лишняя проверка (хотя тут тоже надо профайлить).

Но бросать эксепшн, если «-1» это реально ожидаемый результат во многих случаях (часть «обычного» воркфлоу, а не «exceptional»), действительно не стоит.

Часто алгоритм подразумевает что у тебя есть в контексте true/false. Выполнилось, не выполнилось. Доп проверки нужны как раз чтобы явно бросить эксепшин. Поэтому это двойной удар по перформанцу.
1. Проверка что не получили false в каком-то Ифе, при валидации, в цикле
2. Бросить эксепшин и начинать сбрасывать все состояние треда.
Все вместе это замедляет приложение в десятки раз.

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

А построение логики приложения на эксепшинах считается просто гигантской индусятиной.

Крайности.
Как минимум, не performance-critical код на эксепшенах имеет ряд своих преимуществ (читабельность, отделение «нормального» воркфлоу от хендлинга ошибок в коде, всё такое). Не удалось открыть соединение с БД или подключиться куда-то по сети — кинули эксепшен. Это нормально.
Что касается низкоуровневых алгоритмов вроде той же сортировки — там да, эксепшены вряд ли привнесут что-то хорошее.

построение логики приложения на эксепшинах считается просто гигантской индусятиной

Не погоджусь. Змішування кодів помилок, ексепшенів та глобального стану — ось це жесть. А якщо усе акуратно написано з ексепшенами то і код значно легше читати, і потенційних помилок менше і перформанс не страждає помітно. Просто це інший підхід до організації коду і компілятор викине багато зайвого і не треба буде писати одноманітні if(...) по всьому ланцюгу викликів.

На жаль в реальності добре з еспепшенами написано коди небагатьох бібліотек та фреймворків.

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

З ексепшенами зручно те, що ти обробляєш надзвичайну ситуацію там де це має сенс робити, а не передаєш код помилки з додатковою інформацією по всьому ланцюжку викликів.

Також зауважу, що ексепшени не мають бути заміною кодів помилок. Тобто коли операція завершилася неуспішно — маєш код. Коли сталося щось надзвичайне — маєш ексепшн.

Скажімо я форматую рядки для запису у файл. Нестача пам’яті — це не та помилка яку я в коді форматера можу обробити нормально і муситиму її передавати вище. Якщо ж таке буде ексепшеном то незалежно від того де сталася ця ситуація у мене може бути один універсальний обробник для подібного. І можна наприклад повідомити юзеру, що операція не вдалася і поприбирати з пам’яті якісь об’єкти. Коди вийде значно менше ніж писати if для усіх можливих помилок в усіх гілках логіки.

ти обробляєш надзвичайну

Это две разные ситуации.
В изначальном сообщении было

логики приложения на эксепшине

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

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

В сях тоже есть стандартная сортировка: qsort из stdlib.h. Хоть и, конечно, настолько лаконично не получится.
В плюсах из коробки идёт std::sort из algorithm, который можно в одну строчку вызвать.

А причем здесь синтаксис языка к библиотечной ф-ции ?
PS: Проблема Хаскеля в другом, он делает сортировку не инплейс.
А так конечно синтаксис мощный и лаконичный.

Я скорее говорил о лаконичности кода там и здесь.

Факт в том, что для изучения алгоритмов её таки можно открыть и почитать AS IS

//sort the sub arrays independently
quickSort(arr, low, pivot — 1);
quickSort(arr, pivot + 1, high);

Это нужно запускать в разных потоках, через std::async например

Это точно ускорит. Знать бы еще как это сделать.

Примерно так: ideone.com/GtoTbC

Хотя стандартные асинки довольно фривольны в плане выбора потоков. Насколько я помню, официально стандарт вообще требует от асинка (запущенного с launch policy = async) каждый раз создавать новый поток — что может привести к слишком большому количеству созданных потоков, которые будут «драться» за системные ресурсы, и программа может замедлиться.
А майкрософтовская реализация от стандарта в этом вопросе отходит и запускает эти задачи на виндовом тред пуле. Что может быть хорошо. А может и нет. В общем, надо мерять время с этой модификацией и без неё.

Обычно для распараллеливаний подобного плана используют сторонние библиотеки, вроде Intel TBB. Ну или пишут что-то своё.

Что может быть хорошо. А может и нет.

Как может быть нехорошо, если создание потока — это выделение памяти под стек как минимум, что довольно-таки тяжелый вызов чтобы посчитать 5 элементов. Тредпул — это единственное спасение, ну разве что кроме использования OpenMP, сейчас все компиляторы поддерживают и в С и в С++.

По сравнению с созданием полноценного нового потока, конечно, это лучше, не спорю.

«Может и нет» — тут я скорее имел в виду, что это может не дать ощутымий выигрыш при такой наивной реализации, как в моём примере.
Количество тасок, закидываемых на тредпул, тоже стоит регулировать как-то более по-умному. А то скедьюлить новую таску для тредпула, чтобы отсортировать в ней 5 элементов, тоже такая себе затея.

если создание потока — это выделение памяти под стек как минимум

Предположим у меня массив из 1000 элементов. Могу я запустить одновременно 100 потоков (для каждого элемента отдельно) так чтобы все эти потоки синхронно выполняли какое-либо действие, например обмен местами/упорядочивание ?

Так не получится, потому что обмен местами — это доступ к двум элементам как минимум.
Да и вообще, по потоку на каждый элемент — слишком дорого. Создание потока это довольно недешёвая операция. Потоков должно быть значительно меньше, чем элементов (оптимальное соотношение придётся подбирать экспериментально).

Число потоков должно быть равно числу ядер проца.

Так что там с моим видео? С моим алгоритмом сортировки? Смотреть надо на широком экране, чтобы было более-менее четко видно.

void swap(int* a, int* b)

Навіщо, якщо є std::swap?

int pivot = arr[high]; // pivot

Коментар від бога

int arr[] = {12,23,3,43,51,35,19,45};

std::vector, std::array, нє?

vector, array чи list ? Чи щось ще?
Яка структура даних таке витрима?

Точно не list. Він не про перформанс взагалі.
Якщо розмір масиву такий, що може поміститися на стек, і відомий в компайл-таймі, — краще std::array (хоча і «голий» сішний масив буде ок)
Інакше vector має бути оптимальним варіантом (принаймні на платформах, де достатньо оперативної пам’яті, щоб розмістити у ній весь масив одним contiguous шматком).

якщо на те пішло, то в algorithm є і квік сорт, і партішн

Тут же суть в тому, щоб самому написати алгоритм, нехай і черговий велосипед. А з std алгоритмом тут буде 2 рядки: один для ініціалізації вектору, другий для його сортування.

В залежності від компілятора можна такі мікрооптимізації спробувати:
— зроби swap inline чи макросом, t в ньому зроби глобальною
— заміни i++ на ++і
— часто порівнняня з нулем буває швидше (для цього у процесорів є спеціальна команда) і тому можна цикли зробити від правого елемента до лівого

Також для індексів використовують беззнаковий тип (в С++ для цього спеціально є size_t).

І в цілому це С-код, а не С++.

Зроби ще порівняння з std::sort(arr, arr + n).

Та я не шарю. Дайте код, я его скопипастю в editor. Пор1вняння зроблю.

заміни i++ на ++і

Постинкремент в циклах — быстрее.

Треба асемблерний код дивитися. Я виходжу з того, що пре-інкремент не створює копії значення.

Ассемблер ни при чём. Связано с оптимизацией пайплайна процессора/брэнч предикшэном.

Смотри по «data dependency»...

Ассемблер ни при чём. Связано с оптимизацией пайплайна процессора/брэнч предикшэном.

Компілятори які не дуже вміють в оптимізацію, або яким не сказали оптимізувати для постінкремента роблять копію об’єкта, використовують копію у виразі, а потім модифікують сам об’єкт. Щось типу
i++ стане auto t = i; i+=1, t;
++i буде просто i+=1, i;

Ну так, сучасні компілятори як правило вміють не генерувати зайвого коду. Але для даного прикладу там взагалі усе крім return 0; можна викинути. Тому приклад занадто вже синтетичний.

Чомусь в цьому навіть не сумнівався. Бо ж нема жодної причини передбачати іншу логіку кода окрім як для випадків, коли сам ++ є перевизначеним для конкретного типу даних. Але це дуууже рідко використовується, бо можна втратити розуміння коду.

у Агнера это где-то есть в мануале ?

А що взагалі не так з преінкрементом та постінкрементом — де про це почитати? Бо я відверто не розумію, чому має бути різниця, чи краще сказати, навіщо її запрограмували цю різницю, та де саме вона є, а де нема.

Ця різниця ще з С:
— для пре-інкременту спочатку модифікується операнд, а потім модифіковане значення використовують у виразі
— для пост-інкремента спочатку значення використовують у виразі, а потім модифікують операнд.

a = b++; ===> a = b, b += 1, a;

a = ++b; ==> b += 1, a = b;

Все одно незрозуміло. Якщо a та b — різні значення, то нащо третя дія? Що змінює порядок? Чи мається на увазі, що сама операція «=» має щось повернути? Тоді від цього маразму давно треба було позбутися — через його непередбачуваність людською логікою.

Нема жодного джуна, який би не написав = замість ==. Але саме через цей ідіотський синтаксичний цукор такий вираз проходить тести. Якщо мова генерить помилки, міняти треба мову, а не цілі покоління людей.

Ты видео смотрел мое? В этой теме — мой самый верхний комент. Смотри на широком экране иначе расплывчато и не видно ничего.

Чи мається на увазі, що сама операція «=» має щось повернути? Тоді від цього маразму давно треба було позбутися — через його непередбачуваність людською логікою.

Для плюсовиків (і сішників) все норм, ми давно звикли до цієї поведінки. Жодного разу в продакшені не бачив, щоб вона призводила до якихось страшних наслідків. Хіба що під час написання лабораторок в універі, коли студенти ще не знають мову на достатньому рівні.

У меня на видео (в конце) не сортировка подсчетом. Иначе не понятно отчего обгоняет std::qsort. Ну и кроме того — это может быть косяк моей машины или криво установленный компилятор или код.
Чтобы проверить нужна полностью сторонняя реализация.
Поможешь?

Смотреть видео у меня сейчас времени нет. Да и с имплементацией алгоритмов сортировки я игрался уж очень давно (в продакшене всегда юзал готовые из стандартной библиотеки) — поэтому с алгоритмической частью сейчас помочь вряд ли смогу.
Но если есть конкретные вопросы по тому, как работают отдельные вещи в C++, — могу ответить на них.

А лучше постить код прямо в эту тему. Здесь много знающих людей, мб кому-то из них будет не лень углубиться в алгоритм более серьёзно и помочь конкретно с ним.

А я и не настаиваю, чтобы прямо сейчас. Просто вижу что ты специалист или даже эксперт, потому и прошу, чтобы глянул хоть одним глазом хоть когда-нибудь. Твое мнение очень ценно для меня.
В благодарностях упомяну?
Тем более, что я по прежнему не уверен что этот код можно заливать на гитхаб. На моей машине он-то показывает, а вот что будет на других — неизвестно.

Ну, конкретно в языке C++, его всяких правилах, фичах и т.д. меня может и можно назвать «экспертом». Но в алгоритмах я не так силён. Так что, увы, с ними лучше обратиться к кому-то другому.

Я N (от 0 до MAX) последовательно (при прохождении по исходному массиву) нахожу и тыкаю прямо в результирующий массив вот так res_arr[N] += N
И получается самосортирование.

Якщо a та b — різні значення, то нащо третя дія?

Яка третя дія? Є значення, операція що його модифікує та вираз в якому значення приймає участь.

Що змінює порядок?

Яке саме значення буде використано у виразі — ще не модифіковане, чи вже модифіковане.

Чи мається на увазі, що сама операція «=» має щось повернути?

Як і будь-яка інша операція так. Але це тут ні до чого.

Тоді від цього маразму давно треба було позбутися

Це дуже зрочно і зроблено так само як і для всіх інших операцій. Якщо мова звісно про присвоєння.

Нема жодного джуна, який би не написав = замість ==

Для таких гугл цілу мову запиляв.

цей ідіотський синтаксичний цукор

Це не синтаксичний цукор ніяким боком. Операція присвоєння є звичайною бінарною операцією і як будь-яка операція має результат виконання. Уніфікація і спрощення.

мова генерить помилки

Мова нічого не генерить, вона лише визначає синтаксис та те який результат мають видавати компілятори грубо кажучи.

Варто глянути на асемблер

1. Тимсорт быстрее. Оптимизация у него простая. Незачем рекурсивно вызывать квиксорт на мелких блоках в несколько элементов, а эффективней сортировать слиянием. Экономит на джампах, работает быстрее.
2. Свап можно встроить в тело функции, незачем лишний раз прыгать. Там логики совсем чуть чуть.
3. Рекурсию нужно переписать через циклы. Стек не резиновый.

Верю. А можно код? Тебе это 5 секунд, а я 20 лет в руки с++ не брал.

Порівняй своє рішення тут і подивись рішення інших
leetcode.com/problems/sort-an-array

Это тело функции main
Оно почему-то падает при сортировке 200 000 записей
А golang легко 50 млн сортирует



    char *p;
    if (argc <= 1)
	{
		
		if (argv[0])
			std::cout << "Usage: " << argv[0] << " <number>" << '\n';
		else
			std::cout << "Usage: <program name> <number>" << '\n';
 
		exit(1);
	}
 
	long sz = strtol(argv[1], &p, 10);

    cout << "Hello World  Size of array = " << sz << endl;

   long arr[sz],i;
   long arr0[sz];

   for(i=0;i<sz;i++){
   long d = rand()%sz;
     arr[i]= d;
     arr0[i] = d;
   }

    long n = sizeof(arr)/sizeof(arr[0]); 
    cout<<"Input array"<<endl;
    if(sz<100)  displayArray(arr,n);
    cout<<endl;

    struct timeval tp;
    gettimeofday(&tp, NULL);
    long long ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;

    cout << "Milliseconds from: " << ms << endl;
    quickSort(arr, 0, n-1); 
    gettimeofday(&tp, NULL);
    long long ms2 = tp.tv_sec * 1000 + tp.tv_usec / 1000;
    cout << "Milliseconds passed: " << (ms2-ms)  << endl;
    cout<<"Array sorted with quick sort"<<endl; 
    
    if(sz<100)  displayArray(arr,n); 

Винеси arr і arr0 за межі main.

long arr[sz],i;
long arr0[sz];

по правилам именно С++ это не корректно

Массивы на стеке, который обычно 1мб. Воспользуйся malloc/calloc

Що значить «падає»? Що значить «чомусь»?

Сетктрейс, коредамп.

Хоча всім крім ТС ясно, що це стек.

А можно тупо подсмотреть правильный ответ? Это же классика, всё что можно быстрее — уже сделали.
Единственный момент: в реальности крайне редко сортируют int значения. Потому сортируемые элементы правильно передавать по ссылке, а не по значению. И менять местами соответственно ссылки.

Что НЕ правильно — дёргать функции почём зря. Вызов функции — достаточно тяжёлая операция прерывания потока выполнения, и то что для тебя меньше строчки кода, в реальности вызывает нарушение работы конвейра и отказ от предсказания перехода. Посему, либо пиши инлайн-функции (грубо говоря, макросы), либо тупо откажись от их использования.

Ну и мелочь не очевидная, если ты не держал в руках ассемблер: операция с указателями более быстрая, чем обращение к элементу массива. Потому что при каждом обращении проверяется выход за границы массива. С указателями же тебе просто верят на слово. Разумеется, оптимизаторы могут этот момент для тебя сгладить, но тогда тебе надо знать КАК работают оптимизаторы и соответственно учитывать ещё и их «нюансы», при которых твой код работает не так, как написан. Либо же сразу писать честный высоконагруженный код.

PS. Сортировка — это уже карго-культ. Ты лично вряд ли будешь реализовывать алгоритмы сортировки, просто потому что они есть уже готовые. Ну максимум там несколько значений отсортировать или добавить в уже отсортированный массив. Всё это операции редкие. И суммарное время их выполнения на всех устройствах окажется меньше, чем ты бесцельно потратишь время на их изучение.

PPS. Уже через год ты этого всего и не вспомнишь.

А если я сделал в два раза быстрее? Правда, я не улучшал данное творение, а написал свое решение. Вот только golang позволяет 50 млн. на моем компе, а с++ умирает от 300000

C:\Users\1\home\gohome\proj1>hello 50000000
50000000
--- Unsorted ---
--- Sorted ---
============== OK ===== 1627567320564523800 - 1627567310243315600 ( 10321208200 ) ========
[1 2 3 4]
Hellow,orld!

============== sorting 1627567322927605900 ===============

============== OK ===== 1627567346640781200 ( 23713175300 ) ========

============== MY sorting 1627567346640781200 ===============

============== OK ===== 1627567351273841400 ( 4633060200 ) ========

C:\Users\1\home\gohome\proj1>

И ты уверен, что КРОМЕ тебя никто ничего не написал? Я же посоветовал — взять готовые решения и не париться.

Если мой алгоритм лучше, я хочу его продать. Или как-нибудь по другому монетизировать. А то прозябаю непонятно в каких условиях, несмотря на то, что способен на вот такое двойное ускорение работы википедийно самого применяемого алгоритма сортировки quicksort

Не знаю. Спецом написал его сегодня еще на С++ (в универе на втором курсе немного учил) Там тоже на 100000 записей показывает нехилый прирост. А больше нет. Голанг работает, шуршит, а с++ падает... Весь в непонятках, вот код и выложил.

В C++ варіанті у вас ймовірно stackoverflow. Golang версія працює тому що golang вміє виділяти стек динамічно. Ви можете подивитися скільки пам’яті використовує кожна з версій і перевірити.

Мне, короче, самому не верится. И поэтому я стесняюсь выложить код своего решения.
Буду еще проверять. Аналоги смотреть/гуглить.

Если мой алгоритм лучше, я хочу его продать.

КГ/АМ

Если мой алгоритм лучше, я хочу его продать

Продати ти можеш реалізацію. Але вже саме те, що ти питав поради з вдосконалень ось тут робить його не зовсім твоїм алгоритмом.

1. Ага, так и планирую — реализовать на его основе что-нибудь этакое и продавать.
2. Нет. Я свой алгоритм не выкладывал еще. Это из интернета довольно топорная реализация квиксорт взята. Просто я испугался что он вообще не работает, этот квиксорт. С чем тогда сравнивать свою лялечку?
Возьму (для квиксорта)
long * p = (long *) malloc(1000000*sizeof(long));
Или лучше
long * p = new long[1000000];

Потому что при каждом обращении проверяется выход за границы массива.

очень интересно, расскажи по больше об этом

Почему этот код работает при 100000 записей и не работает при 200000 ?

Про баундс-чекинг — это пение о жабе написало.

Но тем не менее, конструкт arr[i] — это то же самое, что *(а + i). Что очевидно, медленнее, чем *(а++)
Тем более, когда делается ещё и инкремент i.

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

в жаве появились указатели?

В честных языках программирования указатели — достаточно серьёзный инструмент. В виртуальных машинах такого нет. В смысле есть, но тебе так просто это не доступно без потери всех преимуществ Java.

Грубо говоря, указатель — это объект адресной арифметики. А для этого таки должны быть выделены честные области памяти. А собачатины там хватает и в С++, одна только работа с перемещаемой памятью чего стоит, вместе с её возможностью уйти в своп. И это уже совсем не указатели, а ближе к тому что оно в Жабе.

С оптимизацией — да, это то же самое. Но насколько помню в CPP есть проверка на выход за границы, просто так в ногу себе не выстрелишь. В С может быть, может не быть, по дефолту вроде и нету.

Но мой ответ всё тот же — отстать от сортировки вообще совсем. Есть готовые решения, пользовать их. За исключением случаев, когда вы знаете что-то о данных, что может ускорить процесс, грубо говоря, если таки намерены съесть собаку.

Но насколько помню в CPP есть проверка на выход за границы, просто так в ногу себе не выстрелишь

По дефолту её нет.
Есть у стандартных контейнеров, если использовать мембер-функцию .at() вместо оператора[]. Оператор[] ничего не проверяет, во имя быстродействия (чтоб ногу можно было отстрелить максимально быстро, да).

Лишь бы не голову стэку, а то ведь там совсем весело.

Та якось пофігу: чи в голову стеку, чи за межі елементів контейнера — в будь-якому випадку буде боляче

А мой ответ: мне приснился вообще совершенно другой алгоритм сортировки. Я реализовал его сначала на go и обнаружил его превосходство. Удивился. Не поверил. Решил реализовать на с++
И снова...
И я снова не поверил. Вот щас накидали коментаторы очень много разных идей. Воткну их всех в бенчмарк этот самопальный и узнаю все наверняка.

Воткну их всех в бенчмарк этот самопальный и узнаю все наверняка.

Ты ж правильно бенчмарки делай
Там много нюансов:
— горячие/холодные данные
— данные которые хорошо укладываются в кеш и предсказания по выборке памяти

А то может оказаться что результат неверный. И сильно неверный.
Выведи для алгоритма O(...) нотацию — интересно какая оценка у твоего изобретения.

Нотацию сам точно не выведу. Никогда такого не делал. Не пришлось.
А вот что это интересно, тут без всяких сомнений.
Пока что заменил swap(&arr[i]... на std:swap(arr[i]...
Все так же бьем рекорды и падаем.
120 тыщ*8 = 960 (не падает) < 1Mb
130 тыщ*8= > 1Mb (падает)
Стек массив 1Mb
Вроде диагностировали верно. Вот только что дальше?
mallock вроде?
А его можно для size_t ?

Маллок — сишный подход, но если сортировать надо именно инты (примитивные данные без конструкторов и прочего), то покатит. Не забудь только free в конце вызвать :)
«Для size_t» можно (и нужно), ибо malloc принимает size_t. Только учти, что принимает он размер в байтах, а не в кол-ве элементов, так что кол-во элементов нужно будет домножить на sizeof(int):
int* arr = (int*)std::malloc(number_of_elements * sizeof(int));

Но я бы начал с std::vector’а. Результат почти тот же, работать проще.
Можно заполнить вектор данными, а потом взять его .data(), чтобы получить указатель на начало массива, — таким образом даже остальной код менять не придётся.

А может в этом все и дело? Для своего-то алгоритма я беру вектор...
Сейчас все поисправлял (или почти все) и запустил на 130 миллионов так как на 13 миллионов уже запустил и уже получилось отсортировать.
Но это я еще не все оптимизации применил.

Кстати, а если new, delete пару использовать?

Для примитивных типов вроде инта на практике будет примерно то же самое, что с malloc/free.
Хотя ассемблер будет не совсем идентичным, т.к. у new/delete свои вызовы, а у malloc/free — свои. Плюс, оператор new[] может генерировать ещё какой-то эксепшн хендлинг (если эксепшены не выключены в компиляторе).

В общем, надо мерять, будет ли разница ощутимой. При сортировке массивов из миллионов элементов я склоняюсь к мысли, что вообще нет.

Я хочу microsoft переплюнуть. Тоже подстановочный редактор написать — кстати я интуитивно предсказал эту их идею раньше (у меня есть тема об этом, тут на ДОУ)
Только я программирую медленно и неправильно.

Он почти догадался. Посмотри видео. Я же его создавал как произведение искусства. В моем видео целый семиуровневый мир. И еще подземное царство.

Но насколько помню в CPP есть проверка на выход за границы, просто так в ногу себе не выстрелишь.

Це б кардинально протирічило одному з головних принципів С++: «ти не платиш за те, що не використовуєш явно». [i] у вектора чи масива ніяк не відрізняються від *(ptr+i), бо програміст не попросив явно перевірку на вихід за межі. Якби хотів попросити — викликав би спеціальний метод для цього. Плюси завжди дають вистрілити в ногу по дефолту (як і С), просто дають ще і можливіть НЕ вистрелити ціною певної втрати перфомансу (що в С складніше або не можливо).

А в чем отличие arr[i] = val от *arr+i=val от *(arr+i)=val ??
Не могу эти значки гуглить

arr[i] = val — это то же самое, что *(arr + i) = val.
Во втором случае происходит array-to-pointer decay во время операции +: массив кастится к указателю на свой первый элемент (int[N] -> int*), и дальше к этому указателю добавляется сдвиг i. Затем оператор * разыменовывает получившийся указатель, получая как бы ссылку на i-тый элемент массива. И по этой ссылке присваивает значение val. Результат получается идентичным.

*arr + i = val не скомпилится.
Инструкция *arr здесь будет разыменованием указателя (опять же, массив неявно скастится к int*). Следовательно, инструкция *arr вернёт тебе ссылку (не указатель) на самый первый элемент массива. Затем уже к этому элементу добавится значение i. Это произведёт временный объект типа int, имеющий значение arr[0]+i.
Присваивать что-либо временным объектам встроенных типов нельзя: «error: lvalue required as left operand of assignment».

Подписаться на комментарии